AKSZ-算法入门
2024-03-10 17:26:24
发布于：广东
初识算法
算法概述
什么是算法
对一类问题的解决方法
算法（Algorithm）是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。如果一个算法有缺陷，或不适合于某个问题，执行这个算法将不会解决这个问题。不同的算法可能用不同的时间，空间或效率来完成同样的任务。一个算法的优劣可以用空间复杂度与时间复杂度来衡量。
算法中的指令描述的是一个计算，当其运行时能从一个初始状态和（可能为空的）初始输入开始，经过一系列有限而清晰定义的状态，最终产生输出并停止于一个终态。一个状态到另一个状态的转移不一定是确定的。随机化算法在内的一些算法，包含了一些随机输入。
形式化算法的概念部分源自尝试解决希尔伯特提出的判定问题，并在其后尝试定义有效计算性或者有效方法中成形。这些尝试包括库尔特·哥德尔、Jacques Herbrand和斯蒂芬·科尔·克莱尼分别于1930年、1934年和1935年提出的递归函数，阿隆佐·邱奇于1936年提出的λ演算，1936年Emil Leon Post的Formulation 1和艾伦·图灵1937年提出的图灵机。即使在当前，依然常有直觉想法难以定义为形式化算法的情况。 —— 百度百科
算法的五个特点
- 有穷性
能够在一定步骤内终止 - 确切性
每一步必须要有确切的定义（无歧义）
x = x --- y; // 有歧义
x = x - (--y); // 无歧义
- 输入项
需要有输入（输入为0时算法默认） - 输出项
至少有一个输出（无输出时无意义） - 可行性
可以被分解为基本步骤
时间复杂度
概念
算法的执行次数，以 T(n) 表示，其中 n 表示问题的规模
O(n) 可由 T(n) 中的最高次项忽略系数后取得，描述算法时间与问题规模的关系
典例
// 桶排序
int n;
cin >> n;
// 以下时间复杂度为n
for(int i=0;i<n;i++)
{
int x;
cin >> x;
a[x]++
}
// 以下时间复杂度为k
for(int i=0;i<k;i++)
{
// 以下时间复杂度近似为1
for(int j=0;j<a[i];j++)
{
cout << i;
}
}
对数
log(n) = m
即 2m <= n
注意
竞赛中时间复杂度的上限为 108/s
即每秒的最大处理次数约 108 次（理论）
约 5×107（实际）
| 时间复杂度 | O(n) | O(nlogn) | O(n2) | O(3) | O(2n) | O(n!) |
|---|---|---|---|---|---|---|
| n的范围 | n<108 | n<5*105 | n<104 | n<500 | n<25 | n<15 |
空间复杂度
常见的空间复杂度（in 256mb）
| 类型 | long | char | int | bool |
|---|---|---|---|---|
| 所占比特 | 8 | 4 | 4 | 1 |
| 数组最大长度 | 3.2*107 | 6.4*107 | 6.4*107 | 2.5*108 |
模拟
解题步骤
- 审题
不遗漏 + 分析样例 - 分析关系
可以用流程图或表格分析列出 - 编写程序
精简代码，方便调试（函数分割功能） - 调试运行
测试样例，输出中间过程 - 构造数据
选择更复杂，更全面的数据（边界数据、特殊情况等）
##对拍
###概念
使用另一个确定正确的程序运行输入，和测试程序进行输出的对比
###示例程序
// 对拍示例
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");
}
}
全部评论 1
不太对哦， 桶排序里面的 O( n + k ) 是因为桶在取数排序过程中（第二个循环） 。 先扫一遍 O(k)的桶的编号 。 然后对于内部 for(int j=0 ; j<a[i] ; j++)的循环，并不是每一个桶都是扫 n 次 ，而是所有桶加在一起是 n 次 。 所以这里整个时间复杂度是O(n+k) 。
2024-03-10 来自 广东
0
有帮助，赞一个