【算法】算法分析基础 |
您所在的位置:网站首页 › 算法分析主要是分析 › 【算法】算法分析基础 |
前言
衡量算法对计算机资源的使用共有两方面 计算资源(时间) 算法采用的数学模型 算法设计的策略 问题的规模 计算方法: (1)m种元运算; (2)每种元运算执行的时间: t 1 , t 2 , ⋯ , t m t_1,t_2,\cdots,t_m t1,t2,⋯,tm (3)每种元运算执行的次数: e 1 , e 2 , ⋯ , e m e_1,e_2,\cdots,e_m e1,e2,⋯,em (4)元运算与问题规模的关系: ∀ e i ( n ) , 1 ≤ i ≤ m \forall e_i(n),1\leq i\leq m ∀ei(n),1≤i≤m 若用T(n)表示时间复杂度,则有 T ( n ) = ∑ i = 1 m t i × e i ( n ) T(n) = \sum_{i=1}^{m}t_i\times e_i(n) T(n)=∑i=1mti×ei(n)存储资源(空间) 输入数据所占空间 辅助变量所占空间 注:此两方面对应内容为算法分析时需要考虑的,其他方面暂不考虑,如算法代码所占用空间。 数学内容 函数渐进的界 概念设 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上的函数。 若 ∃ c > 0 \exists c>0 ∃c>0和 n 0 > 0 n_0>0 n0>0,使得 ∀ n ≥ n 0 \forall n \geq n_0 ∀n≥n0有 0 ≤ f ( n ) ≤ c g ( n ) 0\leq f(n) \leq cg(n) 0≤f(n)≤cg(n)成立,则称 f ( n ) f(n) f(n)的渐进上界是 g ( n ) g(n) g(n),记作: f ( n ) = O ( g ( n ) ) f(n)=O(g(n)) f(n)=O(g(n))。若 ∃ c > 0 \exists c>0 ∃c>0和 n 0 > 0 n_0>0 n0>0,使得 ∀ n ≥ n 0 \forall n \geq n_0 ∀n≥n0有 0 ≤ c g ( n ) ≤ f ( n ) 0\leq cg(n) \leq f(n) 0≤cg(n)≤f(n)成立,则称 f ( n ) f(n) f(n)的渐进下界是 g ( n ) g(n) g(n),记作: f ( n ) = Ω ( g ( n ) ) f(n)=\Omega(g(n)) f(n)=Ω(g(n))。若 ∀ c > 0 , ∃ n 0 ≥ 0 \forall c>0,\exists n_0\geq 0 ∀c>0,∃n0≥0,使得当 n ≥ n 0 n\geq n_0 n≥n0时有 0 ≤ f ( n ) ≤ c g ( n ) 0 \leq f(n) \leq cg(n) 0≤f(n)≤cg(n)成立,则称函数 f ( n ) f(n) f(n)充分大时,比 g ( n ) g(n) g(n)低阶,记作: f ( n ) = o ( g ( n ) ) f(n)=o(g(n)) f(n)=o(g(n))。若 ∀ c > 0 , ∃ n 0 ≥ 0 \forall c>0,\exists n_0\geq 0 ∀c>0,∃n0≥0,使得当 n ≥ n 0 n\geq n_0 n≥n0时有 0 ≤ c g ( n ) ≤ f ( n ) 0 \leq cg(n) \leq f(n) 0≤cg(n)≤f(n)成立,则称函数 f ( n ) f(n) f(n)比 g ( n ) g(n) g(n)高阶,记作: f ( n ) = ω ( g ( n ) ) f(n)=\omega(g(n)) f(n)=ω(g(n))。若 f ( n ) = O ( g ( n ) ) f(n)=O(g(n)) f(n)=O(g(n))且 f ( n ) = Ω ( g ( n ) ) f(n)=\Omega(g(n)) f(n)=Ω(g(n))时,则记 f ( n ) = Θ ( g ( n ) ) f(n) = \Theta(g(n)) f(n)=Θ(g(n)),则称 g ( n ) g(n) g(n)是 f ( n ) f(n) f(n)的渐进的紧的界。f(n)与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+a1n+a2n2+⋯+aknk称为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} alogbn=nlogba 对于不同底 a a a与 b b b, log a n = Θ ( log b n ) \log_an=\Theta(\log_bn) logan=Θ(logbn) 定理3 对于每一个 b > 1 b>1 b>1和每一个 a > 0 a>0 a>0,有 log b n = o ( n a ) \log_bn=o(n^a) logbn=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)。 利用极限求函数渐进的界 常用公式 洛必达法则 lim n → ∞ f ( n ) g ( n ) = lim n → ∞ f ′ ( n ) g ′ ( n ) \lim_{n\to \infty}\frac{f(n)}{g(n)}=\lim_{n\to \infty}\frac{f'(n)}{g'(n)} n→∞limg(n)f(n)=n→∞limg′(n)f′(n)斯特林公式 n ! = 2 π n ( n e ) n ( 1 + Θ ( 1 n ) ) n! = \sqrt{2\pi n}(\frac{n}{e})^n(1+\Theta(\frac{1}{n})) n!=2πn (en)n(1+Θ(n1))定理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∑ncak=ck=1∑nak ∑ 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∑nak±k=1∑nbk 最常见的数列等差数列{ 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∑nak=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∑naqk=1−qa(1−qn+1),k=0∑nxk=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∑nk1=lnn+O(1) 基本效率类型
分析下列代码的执行效率 计算模型 { 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),则有以下结果: 若 f ( n ) = O ( n ( log b a ) − ϵ ) f(n) = O(n^{(\log_ba)-\epsilon}) f(n)=O(n(logba)−ϵ), ϵ > 0 \epsilon>0 ϵ>0,那么 T ( n ) = Θ ( n log b a ) T(n) = \Theta(n^{\log_ba}) T(n)=Θ(nlogba)若 f ( n ) = Θ ( n log b a ) f(n) = \Theta (n^{\log_ba}) f(n)=Θ(nlogba), 那么 T ( n ) = Θ ( n log b a log n ) T(n) = \Theta(n^{\log_ba}\log n) T(n)=Θ(nlogbalogn)若 f ( n ) = Ω ( n ( log b a ) + ϵ ) f(n) = \Omega (n^{(\log_ba)+\epsilon}) f(n)=Ω(n(logba)+ϵ), ϵ > 0 \epsilon>0 ϵ>0,且对于常数 c < 1 c |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |