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

2020-04-28 本文已影响0人怀老师

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

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

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

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

问题规模：算法求解问题的输入量称为问题的规模，一般用整数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( $log_{2}n$ ),线性阶O(n),线性对数阶O( $nlog_{2}n$ ),平方阶O（ $n^2$ ）,立方阶O（ $n^3$ ）...、k次方阶（ $n^k$ ）、指数阶O（ $2^n$ ）。

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