算法的评价

评价算法优劣的两个重要指标:

1,空间复杂度 S(n)。(Space)依据算法写成的程序在执行时占用的存储单元的长度。

2,时间复杂度 T(n)。(Time)依据算法写成的程序在执行时耗费的时间长度。

 

复杂度的渐进表示法

我们不需要对算法的复杂度做十分精细的计算,随着处理的数据规模的增大,很多时候只需要关心算法复杂度增长的情况。比如T(n) = n² + n,当 n 够大时, T(n) 就等于 n 了。

T(n) = O(f(n)) 表示,对于充分大的 n 时,O(f(n)) 就是 T(n) 的上界。

T(n) = Ω(g(n)) 表示,对于充分大的 n 时,O(f(n)) 就是 T(n) 的下界。

T(n) = θ(h(n)) 表示,对于充分大的 n 时,O(f(n)) 与 T(n) 等价(即是上界,也是下界)。

 

算法复杂度分析

1,若两段算法分别有复杂度 T1(n) = O(f1(n)) 和 T2(n) = O(f2(n)) ,则:

T1(n) + T2(n) = max(O(f1(n)) ,O(f2(n)) )

T1(n) × T2(n) = O(f1(n)) × O(f2(n))

2,若 T(n) 是关于 n 的 k 阶多项式,那么 T(n) = θ(n(k)),即阶次最大的就是复杂度。

3,for 循环的时间复杂度等于循环次数乘以循环体内代码的复杂度。如果循环嵌套,则相乘。

4,if – else 结构的复杂度取决于各个条件里复杂度最大的那个。

发表评论