AKSZ-算法入门

dmy

2024-03-10 17:38:19

发布于：广东

27阅读

0回复

0点赞

第一课

1.算法概念

1.有穷性(不能为死循环)

2.确切性（不能有歧义）

3.输入性（0或无数个）

4.输出性（1个以上）

5.可行性

2.复杂度分析

一.时间复杂度

一个算法的语句执行的次数称为语句频度或者时间频度，表示为T（n）,也就是算法需要执行的运算次数，其中n表示问题的规模；
时间复杂度被我们称为记为O（n）
例如:

int n;
cin>>n;
cout<<n;
n++;

T(3);O(1)

aaaa...*a=a^x=n
x=log a n;

(1).常见的时间复杂度

O(1),O(logn),O(n),O(nlogn),O(n!)

运算量	最大规模	速度扩大两倍后
n!	11	11
2ⁿ	26	27
n³	464	584
n²	10000	14142
nlog2n	4.5*10⁶	8.6*10⁶
n	100000000	200000000

如果n最大是10⁸，那算法复杂度最多O(n);

如果n最大是10⁴，那算法复杂度最大O(n²)

二.空间复杂度

算法所使用的额外的空间大小

时间复杂度-->TLE

空间复杂度-->MLE

三.模拟算法

1.审题立意

不遗漏地把题目中的所有条件都提取出来并分析题目样例

2.分析关系

分析给出的各个条件直接的关系,最好用流程图或简单列表列出

3.编写程序

用相应的语言，逐步求精的方法描述具体的算法

4.调试运行

调试代码并测试样例，如输出中间重要过程，观察中间过程是否正确

5.构造数据

构造一些更复杂，更全面的测试数据来检查程序的正确性

对拍

while(true){
	system("数据.exe>test.in");
	system("伐木工.exe<test.in>my.out");
	system("暴力.exe<test.in>std.out");
	if(system("fc my.out std.out"))//返回非0表示有差异
		system("pause");
}

有帮助，赞一个

去预览

0/2000

全部评论 1

深圳福田CBD黄老师
不错，可以用自己的话来解析知识点。但是可以尝试学学用 $$ 来实现Latex公式。

2024-03-10 来自广东
1

第一课