Machine World | Math World

记录实验过程

【算法设计与分析】概述(三)--- <分析基础>

【背景】

        在概述(二)中,我们着重介绍了对\( O\)的分析,事实上还有很多关于复杂度的分析,以及重要结论,但眼下无论是工业界或是学界都着重分析\(O \),篇幅有限我们在概述(二)中点到即止,详细的分析法还请查阅《计算机程序设计艺术》,本文针对\( O\)的分析回顾一下中学数学基础,方便今后对时间复杂度进行分析。

【标准记号与常用函数】

单调函数

单调递增:

\(m \leq n \Rightarrow f(m) \leq f(n) \)

单调递减:

\( m \leq n \Rightarrow f(m) \geq f(n)\)

严格单调递增:

\( m < n \Rightarrow f(m) < f(n)\)

严格单调递减:

\( m < n \Rightarrow f(m) > f(n) \)

取整函数

向下取整:

\( \lfloor x \rfloor\)

向上取整:

\(\lceil x \rceil \)

取整函数若干性质

  • \( x – 1 < \lfloor x \rfloor \leq x \leq \lceil x \rceil < x + 1\)
  • \( \lfloor n / 2 \rfloor + \lceil n / 2 \rceil = n\)
  • 对于\( n \geq 0, a,b > 0\)有:

\( \lceil \lceil n / a \rceil / b \rceil = \lceil n / ab \rceil\)

\( \lfloor \lfloor n/a\rfloor / b\rfloor = \lfloor n / ab \rfloor\)

\( \lceil a / b \rceil \ leq (a+(b-1)) / b\)

\( \lfloor a / b \rfloor \geq (a-(b-1)) /  b\)

\( f(x) = \lfloor x \rfloor, g(x) = \lceil x \rceil为单调增函数\)

多项式函数

  • \( p(n) = a_0 + a_1n + a_2n^2+ \dots + a_dn^d; a_d > 0\)
  • \( p(n) = \Theta(n^d)\)
  • \( f(n) = O(n^k) \Leftrightarrow f(n)多项式有界\)
  • \( f(n) = O(1) f(n) \leq c\)
  • \( k \geq d \Rightarrow p(n) = O(n^k)\)
  • \( k \leq d \Rightarrow p(n) = \Omega(n^k)\)
  • \( k > d \Rightarrow p(n) = o(n^k)\)
  • \( k < d \Rightarrow p(n) = \omega(n^k)\)

指数函数

对于正整数\( m,n\)和实数a > 0

  • \( a^0 = 1\)
  • \( a^1 = a\)
  • \( a^{-1} = \frac{1}{a}\)
  • \( (a^m)^n = a^{mn}\)
  • \( (a^m) ^ m = (a^n)^m\)
  • \( a^ma^n = a^{n + m}\)
  • \( a > 1 \Rightarrow a^n 为单调递增函数\)
  • \(\begin{align} a > 1 \Rightarrow \lim_{n \rightarrow \infty}\frac{n^b}{a^n} = 0 \Rightarrow n^b = o(a^n)\end{align}\)
  • \(\begin{align} e^x = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \cdots = \sum_{i=0}^{\infty}\frac{x^i}{i!}\end{align}\)
  • \( e^x \geq 1 + x\)
  • \( |x| \leq 1 \Rightarrow 1 + x \leq e^x \leq 1+x + x^2\)
  • \(\begin{align}\lim_{n \rightarrow \infty }(1+ \frac{x}{n})^n = e^x \end{align}\)

对数函数

  • \( \log n = \log_2 n\)
  • \( \lg n = \log_{10} n\)
  • \( \ln n = \log_e n\)
  • \( \log^k n = (\log n)^k\)
  • \( \log \log n = \log(\log n)\)

对所有实数\( a>0, b > 0, c> 0,和n\)有:

  • \( a = b^{\log_b a}\)
  • \( \log_c(ab) = \log_c a + \log_c b\)
  • \( \log_b a^n = n \log_b a \)
  • \( \log_b a = \frac{log_c a}{log_c b}\)
  • \( \log_b (1 /a) = -log_b a\)
  • \( \log_b a = \frac{1}{log_a b}\)
  • \( a^{log_b c} = c^{log_b a}\)
  • \(  |x| \leq 1 \Rightarrow \ln(1+x) = x – \frac{x^2}{2} + \frac{x^3}{3} – \frac{x^4}{4}+\frac{x^5}{5} + \cdots + (-1)^{n-1}\frac{x^n}{n} \)
  • \( for x > -1, \frac{x}{1+x} \leq \ln(1+x) \leq x\)
  • \( \begin{align}for any a > 0, \lim_{n\rightarrow \infty} \frac{\log^b n }{(2^a)^{\log n}} = \lim_{n \rightarrow \infty} \frac{\log^b n}{n ^a} = 0 \Rightarrow \log^b n = o(n^a)\end{align}\)

阶乘函数

\( n! = \begin{cases}1&n = 1\\n(n-1)! & n > 0\end{cases}\)

Stirling's approximation:

\( n! = \sqrt{2\pi n}(\frac{n}{e})^n(1+\Theta(\frac{1}{n}))\)

  • \( n! = o(n^n)\)
  • \( n! = \omega(2^n)\)
  • \( \log(n!) = \Omega(n\log n)\)
  • \( n! = \sqrt{2\pi n}(\frac{n}{e})^n e^{\alpha_n},其中\frac{1}{12n+1} < \alpha_n < \frac{1}{12n}\)

【数列求和公式】

等差数列求和:

\( S_n = \frac{(a_1 + a_n)n}{2} = na_1 + \frac{n(n-1)}{2}d\)

等比数列求和:

\( S_n = \frac{a_1(1-q^n)}{1-q} = \frac{a_1 – a_nq}{1-q} (q\neq 0)\)

【非递归算法复杂性分析】

基础:

(1) for/while循环

    循环体内计算时间*循环次数;

(2) 嵌套循环

    循环体内计算时间*所有循环次数;

(3) 顺序语句

    各语句计算时间相加;

(4) if-else语句

    if语句计算时间和else语句计算时间的较大者。

一般步骤:

1. 决定用哪个(或哪些)参数作为算法问题规模的度量

    可以从问题的描述中得到。

2. 找出算法中的基本语句

    通常是最内层循环的循环体。

3. 检查基本语句的执行次数是否只依赖于问题规模

    如果基本语句的执行次数还依赖于其他一些特性,则需要分别研究最好情况、最坏情况和平均情况的效率。

4. 建立基本语句执行次数的求和表达式

    计算基本语句执行的次数,建立一个代表算法运行时间的求和表达式。

5. 用渐进符号表示这个求和表达式

    计算基本语句执行次数的数量级,用大O符号来描述算法增长率的上限。

例子:

int m = 0, i, j;
for(i = 1; i <= n; i++){
    for(j = 2*i; j <=n; j++){
        m++;
    }
}

解法1:算法的基本操作为:\( m++\),\( m\)的初值为0, \( m\)的值即为执行次数.由于内循环从\(2*n \sim n \),所以\( i\)的最大值满足\( 2i \leq n\),即\(i \leq n/2 \):

\(\begin{align}m &= \sum_{i=1}^{n/2} \sum_{j = 2i}^n 1 \\&= \sum_{i=1}^{n/2} (n-2i+1) \\&= n\cdot\frac{n}{2}-2\sum_{i=1}^{n/2} + \frac{n}{2} \\ &=\frac{n^2}{2} – \frac{n}{2}(\frac{n}{2} + 1) + \frac{n}{2} = \frac{n^4}{4}\end{align}\)

解法2:\(n\)为偶数, 外循环执行\( n / 2\)次. 外循环\(i=1\)时, 内循环\(j\)从\(2\)变到\(n\), 语句\(m++\)执行\(n-1\)次; \(i=2\)时, 内循环执行\(n-3\)次; ……; \(i=n/2\)时, 内循环执行1次.

故:

\(m = (n-1) + (n-3) + \dots + 3 + 1 = \frac{n^2}{4}\)

即:

\(T(n) = O(n^2)\)

【递归算法复杂性分析】

基础:

对递归算法时间复杂性的分析, 关键是根据递归过程建立递推关系式, 然后求解这个递推关系式》

例1:

int factorial(int n){
    if(n == 0) return 1;
    return n * factorial(n-1);
}

可得递推式:

\(T(n) = \begin{cases}1 & n=0 \\ T(n-1) + 1 &n>0\end{cases}\)

解之:

\(T(n) = n \)

例2:

void Hanoi(int n, char A, char B, char C){
    if(n == 1){
        printf("A->C");
    }else{
        Hanoi(n-1, A, C, B);
        printf("A->C");
        Hanoi(n-1, B, A, C);
    }
}

可得递推式:

\(T(n) = \begin{cases}1 & n =1 \\ 2T(n-1) + 1\end{cases}\)

解之:

\(\begin{align}T(n) &=2T(n-1) + 1\\&=2(2T(n-2) + 1)  + 1\\&= 2^2T(n-2)+ (2 + 1) \\&=\dots \\&= 2^{n-1} + 2^{n-2} + \dots + 2^2 + 2 + 1 \\&=2^n -1 \\&=O(2^n)\end{align}\)

扩展递归

扩展递归(extended recusion)是一种常用的求解递推关系式的基本技术,扩展就是将递推关系式中等式右边的项根据递推式进行替换,扩展后的项被再次扩展,依次下去,会得到一个求和表达式,然后可以借助求和技术进行求解。

例:求解下述递推式时间复杂性:

\( T(n) = \begin{cases} 7 & n =1 \\ 2T(n /2) + 5n^2 & n > 1\end{cases}\)

解:

简单起见:设\( n = 2^k\),将递推式进行扩展:

\(\begin{align}T(n) &= 2T(n/2)+ 5n^5 \\&=2(2T(n/4)+5(n/2)^2) + 5n^2 \\ &= \dots \\ &=2^kT(1) + 2^{k-1} \times 5(frac{n}{2^{k-1}})^2 + \cdots + 2\times5(\frac{n}{2})^2 + 5n^2 \\&=7n + 5\sum_{i=0}^{k-1}(n^2)(2^i) \\&= 7n + 5n^2(2-\frac{1}{2^{k-1}}) \\&= 10n^2 – 3n \\&\leq 10n^2 \\&= O(n^2)\end{align}\)

【概述小结】

算法与程序

  1. 算法基本概念和性质

  2. 算法描述方法

问题求解过程

算法复杂性分析

  1. 算法复杂性基本概念

  2. 算法复杂性的渐近性态

  3. 算法渐近分析记号的定义和性质

  4. 非递归算法和递归算法的复杂性分析

【参考文献】

  • 2019年广西师范大学计算机与信息工程学院算法设计与分析课件[OL].李志欣教授.2019.01.01

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注