衡量算法对计算机资源的使用共有两方面

设 T ( n ) T(n) T(n)是算法 A A A的时间复杂性函数， n n n是问题规模, n ≥ 0 n\geq 0 n≥0且 n ∈ Z n\in Z n∈Z，一般有 n → ∞ n \to \infty n→∞时， T ( n ) → ∞ T(n)\to \infty T(n)→∞。如果存在 T ′ ( n ) T'(n) T′(n)，使得当 n → ∞ n \to \infty n→∞时，有 T ( n ) − T ′ ( n ) T ( n ) → 0 \frac{T(n)-T'(n)}{T(n)}\to0 T(n)T(n)−T′(n)​→0，那么， T ′ ( n ) T'(n) T′(n)是 T ( n ) T(n) T(n)当 n → ∞ n\to \infty n→∞时的渐进态或称 T ′ ( n ) T'(n) T′(n)为算法 A A A当 T ( n ) → ∞ T(n)\to \infty T(n)→∞的渐进复杂性。

设f和g是定义域为自然数集N上的函数。

定理1 传递性 设f、g、h是定义域为自然数集合 如果 f = O ( g ) f = O(g) f=O(g)且 g = O ( h ) g=O(h) g=O(h)，那么 f = O ( h ) f=O(h) f=O(h); 如果 f = Ω ( g ) f = \Omega(g) f=Ω(g)且 g = Ω ( h ) g=\Omega(h) g=Ω(h)，那么 f = Ω ( h ) f=\Omega(h) f=Ω(h); 如果 f = Θ ( g ) f = \Theta(g) f=Θ(g)且 g = Θ ( h ) g=\Theta(h) g=Θ(h)，那么 f = Θ ( h ) f=\Theta(h) f=Θ(h); 定理2 假设f和g是定义域为自然数集合的函数，若对于某个其他的函数h，有 f = O ( h ) f=O(h) f=O(h)和 g = O ( h ) g=O(h) g=O(h)，那么 f + g = O ( h ) f+g=O(h) f+g=O(h)。 多项式函数 设k为常数， f ( n ) = a 0 + a 1 n + a 2 n 2 + ⋯ + a k n k f(n) = a_0 + a_1n +a_2n^2+\cdots+a_kn^k f(n)=a0​+a1​n+a2​n2+⋯+ak​nk称为k次多项式，其中， a k ≠ 0 a_k\not =0 ak​​=0。显然有 f ( n ) = Ω ( n k ) f(n)= \Omega(nk) f(n)=Ω(nk)，再根据定理2的推广结果不难证明 f ( n ) = O ( n k ) f(n)= O(n^k) f(n)=O(nk)，所以有 f ( n ) = Θ ( n k ) f(n) = \Theta(n^k) f(n)=Θ(nk)。 对数函数当 b^x = n，有 \log_{b}n = x。对数函数有如下性质： a log ⁡ b n = n log ⁡ b a a^{\log_{b}n} = n^{\log_{b}a} alogb​n=nlogb​a 对于不同底 a a a与 b b b， log ⁡ a n = Θ ( log ⁡ b n ) \log_an=\Theta(\log_bn) loga​n=Θ(logb​n) 定理3 对于每一个 b > 1 b>1 b>1和每一个 a > 0 a>0 a>0，有 log ⁡ b n = o ( n a ) \log_bn=o(n^a) logb​n=o(na)。 定理4 对每个 a > 1 a>1 a>1和每个 k > 0 k>0 k>0，有 n k = o ( a n ) n^k=o(a^n) nk=o(an)。

定理5 设 f f f和 g g g是定义域为自然数集合 N N N上的非负函数。 如果 lim ⁡ n → ∞ f ( n ) g ( n ) \lim_{n\to \infty}\frac{f(n)}{g(n)} limn→∞​g(n)f(n)​存在，并且等于某个常数 c > 0 c>0 c>0，那么 f ( n ) = Θ ( g ( n ) ) f(n) = \Theta(g(n)) f(n)=Θ(g(n))。 如果 lim ⁡ n → ∞ f ( n ) g ( n ) \lim_{n\to \infty}\frac{f(n)}{g(n)} limn→∞​g(n)f(n)​=0，那么 f ( n ) = o ( g ( n ) ) f(n) = o(g(n)) f(n)=o(g(n))。 如果 lim ⁡ n → ∞ f ( n ) g ( n ) \lim_{n\to \infty}\frac{f(n)}{g(n)} limn→∞​g(n)f(n)​=+ ∞ \infty ∞，那么 f ( n ) = ω ( g ( n ) ) f(n) = \omega(g(n)) f(n)=ω(g(n))。 阶乘函数 关于阶乘函数有 n ! = o ( n n ) , n ! = ω ( 2 n ) , l o g ( n ! ) = Θ ( n log ⁡ n ) n!=o(n^n),n!= \omega(2^n),log(n!)= \Theta(n \log n) n!=o(nn),n!=ω(2n),log(n!)=Θ(nlogn)成立。(斯特林公式可证明)

∑ k = 1 n c a k = c ∑ k = 1 n a k \sum_{k=1}^{n}ca_k = c\sum_{k=1}^{n}a_k k=1∑n​cak​=ck=1∑n​ak​ ∑ k = 1 n ( a k ± b k ) = ∑ k = 1 n a k ± ∑ k = 1 n b k \sum_{k=1}^{n}(a_k\pm b_k) = \sum_{k=1}^{n}a_k\pm \sum_{k=1}^{n}b_k k=1∑n​(ak​±bk​)=k=1∑n​ak​±k=1∑n​bk​

等差数列{ a k a_k ak​} ∑ k = 1 n a k = n ( a 1 + a n ) 2 \sum_{k=1}^{n}a_k = \frac{n(a_1+a_n)}{2} k=1∑n​ak​=2n(a1​+an​)​ 等比数列{ a q k aq^k aqk} ∑ k = 0 n a q k = a ( 1 − q n + 1 ) 1 − q , ∑ k = 0 n x k = a ( 1 − x n + 1 ) 1 − x \sum_{k=0}^{n}aq^k = \frac{a(1-q^{n+1})}{1-q},\sum_{k=0}^{n}x^k = \frac{a(1-x^{n+1})}{1-x} k=0∑n​aqk=1−qa(1−qn+1)​,k=0∑n​xk=1−xa(1−xn+1)​ 调和级数{ 1 k \frac{1}{k} k1​} ∑ k = 1 n 1 k = ln ⁡ n + O ( 1 ) \sum_{k=1}^{n}\frac{1}{k} = \ln n+O(1) k=1∑n​k1​=lnn+O(1)

图源：ppt

分析下列代码的执行效率 核心操作：通过加法和乘法运算求 C [ i , j ] C[i,j] C[i,j]; 运算次数： ∑ k = 0 n − 1 1 \sum_{k=0}^{n-1}1 ∑k=0n−1​1 T ( n ) = ∑ i = 0 n − 1 ∑ j = 0 n − 1 ∑ k = 0 n − 1 1 = n 3 = Θ ( n 3 ) T(n) = \sum_{i=0}^{n-1} \sum_{j=0}^{n-1} \sum_{k=0}^{n-1} 1 =n^3=\Theta(n^3) T(n)=i=0∑n−1​j=0∑n−1​k=0∑n−1​1=n3=Θ(n3)

计算模型 { f ( n ) = 1 n = 0 f ( n ) = n f ( n − 1 ) n > 0 \left\{ \begin{array}{lr} f(n)=1 &n=0 & \\ f(n)=nf(n-1) & n>0 & \end{array} \right. {f(n)=1f(n)=nf(n−1)​n=0n>0​​ 算法分析 T ( n ) = 1 + T ( n − 1 ) = ⋯ = n = Θ ( n ) T(n) = 1 + T(n-1) =\cdots= n = \Theta(n) T(n)=1+T(n−1)=⋯=n=Θ(n)

设 a ≥ q , b ≥ 1 a\geq q,b\geq 1 a≥q,b≥1为常数， f ( n ) f(n) f(n)为函数， T ( n ) T(n) T(n)为非负整数，且 T ( n ) = a T ( n b ) + f ( n ) T(n)=aT(\dfrac{n}{b})+f(n) T(n)=aT(bn​)+f(n)，则有以下结果：