数据结构重学日记（二）算法和相关概念

算法

算法是对问题求解步骤的描述，通过有限序列的指令来实现。

数据结构 + 算法 = 程序。

通常，算法都具备以下五种特性：

有穷性

有限步之后结束，不会出现无线循环。

确定性

算法的每条指令都有明确的意义，不会产生二义性。

可行性

算法在当前环境条件下可以通过有限次运算实现。
比如受限于计算机的计算能力，有些算法虽然理论上可行，但实际上无法完成。

输入

能被计算机处理的各种类型的数据，如数字、音频、图像等。

输出

一至多个程序输出结果。

算法

算法复杂度

时间复杂度

• 用来衡量算法随着问题规模增大，算法执行时间增长的快慢的一个函数。
• 时间复杂度是问题规模的函数： 记作 T(n)，时间复杂度主要分析 T(n)的数量级。
• T(n) = O(f(n))，f(n)是算法中基本运算的频度，一般考虑最坏情况下的时间复杂度。

计算方法

空间复杂度

• 衡量算法随问题规模增大，算法所需空间的增长的快慢。
• 是问题规模的函数： S(n) = O(g(n))。

时间复杂度