AKSZ-算法入门

C+Mouger+xhx

2024-07-03 19:11:17

发布于：广东

19阅读

0回复

0点赞

算法

五大特性

1有穷性明确运行次数（不为死循环）
2确切性程序中不出现歧义
3输入项 0~n个输入均可
4输出项必须有输出，无输出的算法无意义
5可行性输出要正确，在有效时间中完成

时间复杂度

T（）为程序运行的次数
O（）为T（）最高项去系数

数据量推算法复杂度

竞赛通常限制时长为1s，一般运行10^8次左右。以下为常用时间复杂度。

时间复杂度	数据大小
O(n)	<5*10^7
O(n logn)	<5*10^5
O(n^2)	<5000
O(n^3)	<500
O(2^n)	<20
O(n!)	<10

两种数据点超出时空范围的报错：

TLE：程序超时（死循环/算法繁琐）
MLE：超内存（空间过大）

模拟算法

1 审题立意不遗漏提取题目条件，分析题目样例

2 分析关系最好用流程图或表格列出各条件关系

3 编写程序用相应语言，逐步求精的方法描述具体算法

例：

时间复杂度	算法
O(n^3)	暴力
O(n^2)	枚举
O(n)	dp(动态规划)

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

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

对拍

自己给数据点，将两种不同复杂度的算法的结果进行对比。

代码：

#include<bits/stdc++.h>
	using namespace std;
	int main(){
	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"))
			system("pause");
	}
	return 0;
	}