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))。
网友评论