数据结构与算法：基础篇(三)：算法比较及复杂度计算

一、算法定义

算法就是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每个指令表示一个或者多个操作。

二、算法特性

1. 输入输出 - 算法是为了解决问题而存在的，必须有输入和输出
2. 有穷性 - 有限次执行下得到结果
3. 确定性 - 不同的输入都有其对应确定的结果
4. 可行性

三、算法设计要求

1. 正确性
2. 可读性
3. 健壮性
4. 时间效率高和存储量低

设计一个算法必须先保证正确，可读以及健壮性，然后再考虑时间效率以及存储量

四、时间复杂度

程序时间计算因素：

1. 算法输入时间
2. 编译可执行代码
3. 执行指令
4. 执行重复的指令

一个算法的时间复杂度定性描述该算法的运行时间，并且一个算法花费的时间与算法中语句执行次数成正比。

四、大O表示法

时间复杂度常用大O符号表述；大O符号表述的规则：

1. 用常数1取代运行时间中所有常数 3->1 O(1)
2. 在修改运行次数函数中，只保留最高阶项 n³⁺²ⁿ2+5 -> O(n^3)
3. 如果再最高阶存在且不等于1，则去除这个项目相乘的常数 2n^3 -> n^3

五、时间复杂度常用术语

1. 常数阶 -> O(1)
2. 线性阶 -> O(n)
3. 平方阶 -> O(n^2)
4. 对数阶 -> O(logn)
5. 立方阶 -> O(n^3)
6. nLog阶 -> O(nlogn)
7. 指数阶(不考虑) -> O(2^n)或者O(n!) 除非n非常小，否则会造成噩梦般的时间消耗，不切实际，一般不考虑

示例：

阶.png

六、空间复杂度

程序空间计算因素：

1. 寄存本身的指令
2. 常数
3. 变量
4. 输入
5. 对数据进行操作所需要的辅助空间

算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度计算公式记做：

S(n) = n(f(n)), 其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数。

在考量算法的空间复杂度，主要考虑算法执行时所需要的辅助空间。

空间复杂度同样用大O表示法。

溪浣双鲤的技术摸爬滚打之路