数据结构与算法第三课-算法和算法分析

1.4.1 算法的定义及特性

        算法（Algorithm）是为了解决某类问题而规定的一个有限长的操作序列。

        算法的五个特性：有穷性、确定性、可行性、输入、输出。

1.4.2 评价算法优劣的基本标准

        一个算法的优劣从四个方面评价：正确性、可读性、健壮性、高效性。

1.4.3 算法的时间复杂度

            频度：一条语句的重复执行次数称作语句的频度。

            问题规模：算法求解问题的输入量称为问题的规模，一般用整数n表示。

            数量级：（Order of Magnitude）简称“O”。我们所说的“大O表示法”就是这个O。

            时间复杂度：是该算法的执行时间，记作T(n)，T(n)是该算法所求解规模n的函数。当问题的规模n趋向无穷大时，T(n)的数量级称为算法的渐进时间复杂度，记作T(n) = O(f(n))。它表示，随问题规模n的增大，算法执行时间的增长率和f(n)增长率相同，简称时间复杂度。

            常见的时间复杂度：递增排列：常数阶O(1),对数阶O(),线性阶O(n),线性对数阶O(),平方阶O（）,立方阶O（）...、k次方阶（）、指数阶O（）。

1.4.4 算法的空间复杂度

        空间复杂度（Space Complexity）:作为算法所需存储空间的量度，简称空间复杂度。记作 S(n) = O（f(n)）。