算法

算法是为解决某一问题对数据运算步骤的序列

特点

1. 有穷性：算法在有限的步骤之内能执行完毕
2. 确定性：算法的每一个步骤都有唯一的解释，无二义性
3. 可行性：算法的每一个步骤能够在有限的时间内完成
4. 输入：算法有零个或多个外部输入
5. 输出：算法有一个或多个输出

算法分析

算法在正确的情况下，对其优劣的分析

好的算法

• 对应的程序所耗时间少
• 对应的程序所耗空间少
• 算法结构性好、易读、易移植和调试

语句的频度

可执行语句在算法或程序中重复执行的次数

时间复杂度

算法中可执行语句的频度之和，记为$T(n)$，是问题规模的函数

$n$为问题的规模：输入数据量的大小

当n->∞时，取$T(n)$等于$T(n)$的同阶无穷大$O(f(n))$，表示$T(n)$量级。当问题规模$n$增大，算法执行时间的增长率和$f(n)$的增长率相同

对于较为复杂的算法，可分段分析其时间复杂度：$T_1(N)=O(f(n))$ ,$T_2(N)=O(g(n))$

1、若两部分的问题规模相等，则总的$T(n)=O(max(f(n),g(n)))$

2、若两部分的问题规模不相等，则总的$T(m,n)=O(f(m)+g(n))$

空间复杂度

$D(n)$：执行算法所占存储空间的量级

数据结构+算法=程序

与数据结构关系

算法设计：取决于选定的逻辑结构

算法实现：依赖于采用的存储结构

与程序区别

1、算法与计算机无关，但程序依赖于具体的计算机语言

2、算法必须是有穷的，但程序可能是无穷的

3、算法可以忽略一些语法细节问题，将重点放在解决问题的是思路上，但程序有严格的语法规则必须遵守

本文链接：https://shengto.top/data_structure/ds_2.html

转载时须注明出处及本声明