【算法】复杂度的渐近表示

(O(f(n))):

(T(n)=O(f(n)))表示存在常数(C>0),(n_0>0),使得当(n>n_0)时,总有(T(n)<=Cf(n))

(Omega(f(n)))

(T(n)=Omega(f(n)))表示存在常数(C>0),(n_0>0),使得当(n>n_0)时,总有(T(n)>=Cf(n))

(Theta(f(n)))

(Theta(f(n)))表示同时有(T(n)=O(f(n)))(T(n)=Omega(f(n)))

一般取能找到的最小的上界和最大的下界。

程序员的直觉,当有一个算法是(O(n^2))的,下意识想能不能变成(O(nlogn))

两段代码相加与相乘

若两段算法分别有复杂度(T_1(n)=O(f_1(n)))(T_2(n)=O(f_2(n))),则
(T_1(n)+T_2(n)=max(O(f_1(n)),O(f_2(n))))
(T_1(n)·T_2(n)=O(f_1(n)·f_2(n)))

原文地址:https://www.cnblogs.com/maxwell-maxwill/p/12301666.html