时间复杂度学习(上)

2018-12-03 本文已影响0人 HelloWodee

2018年10月9日

1，定义

时间复杂度一般采用大O标记法, 即 $T(n)=O(f(n))$ , 其中T(n)表示代码运行时间；n表示数据规模大小；f(n)表示每行代码执行次数总和， $O$ 表示T(n)与f(n)的正比关系。大 $O$ 时间复杂度实际上并不具体表示代码的真正运行时间，而是表示代码执行时间随数据规模增长的变化趋势。

在大 $O$ 表示分析中，低阶项和常数项都可以省略，只保留最高阶项即可；如 $f(n)=2n+2$ 在大 $O$ 标记法中记为 $T(n)=O(n)$ ，而对于形如 $f(n)=2n^2 +2n+3$ 表示为 $T(n)=O(n^2)$ 。

2，时间复杂度分析

关注循环次数多的代码
```
public int accumulate(int n) {
    int sum = 0;
    int i = 1;
    for (; i <= n; i++) {
        sum += i;
    }
    return sum;
}
```
其中for循环内的代码执行n次，而其余代码执行1次，与n的大小无关，忽略常数项，该段代码的时间复杂度为 $O(n)$ 。

加法法则

总复杂度为量级最大的那段代码的复杂度，抽象为公式为：

若 $T_{1}(N)=O(f(n))$ ， $T_{2}(N)=O(g(n))$ ，
那么
$T(N)=T_{1}(N)+T_{2}(N)=O(f(n))+O(g(n))$
$=max(O(f(n)),O(g(n)))$

public int accumulate(int n) {
   int sum1 = 0;
   for (int i = 1; i <= 100; i++) {
       sum1 += i;
   }

   int sum2 = 0;
   for (int i = 1; i <= n; i++) {
       sum2 += i;
   }

   int sum3 = 0;
   for (int i = 1; i <= n; i++) {
       for (int j = 1; j <= n; j++) {
           sum3 += i * j;
       }
   }
   return sum1 + sum2 + sum3;
}

其中sum1段的代码循环执行了100次，与n无关。sum2段代码的复杂度为 $O(N)$ ，sum3段的代码复杂度为 $O(N^2)$ ；根据加法法则，我们只去其中最大量级的复杂度，所以该段代码的时间复杂度为 $O(N^2)$ 。

乘法法则

嵌套代码的复杂度等于嵌套内外代码复杂度的乘积，抽象为公式为：

若 $T_{1}(N)=O(f(n))$ ， $T_{2}(N)=O(g(n))$ ，那么 $T(N)=T_{1}(N)*T_{2}(N)=O(f(n)*g(n))$

public int accumulate(int n) {
    int result = 0;
    for (int i = 1; i <= n; i++) {
        result += f(i);
    }
    return result;
}

private int f(int n) {
    int sum = 0;
    for (int i = 1; i <= n; i++) {
        sum += i;
    }
    return sum;
}

其中accumulate方法与f方法的时间复杂度都为 $O(N)$ ，但是f嵌套在accumulate中，所以整段代码的复杂度就为： $T(N)=T_{1}(N)*T_{2}(N)=O(N * N)=O(N^2)$

3，常见时间复杂度量级

度量级	大 O 表示
常量阶	$O(1)$
对数阶	$O(logN)$
线性阶	$O(N)$
线性对数阶	$O(NlogN)$
平方阶	$O(N^2)$
立方阶	$O(N^3)$
指数阶	$O(2^n)$
阶乘阶	$O(N!)$

常见的时间复杂度有常量阶、对数阶、线性阶、线性对数阶以及平方阶，常量阶、线性阶与平方阶在第二节中已经分析，不再赘述；而一些高效的排序算法的时间复杂度就是线性对数阶，如快速排序，归并排序以及堆排序等。
对数阶

我们所熟知的二分查找的复杂度就是 $O(logN)$ ，以下通过一段代码来分析对数阶复杂度：
```
public int test(int n) {
    int res = 1;
    while (res <= n) {
        res *= 2;
    }
    return res;
}
```
该段代码是求 $2^x=n$ 的解，更确切的说，是找出 $2^x$ 在小于或等于n的范围内最接近n的x的值；其中 $x=\log_{2}n$ ，即while循环体内代码要执行 $\log_{2}n$ 次，即其时间复杂度为 $O(\log_{2}n)$ 。

若把循环体内代码 res *= 2 改为 res *= 3 ，不难分析出其时间复杂度就变为 $O(\log_{3}n)$ ；但是为什么所有对数阶的时间复杂度都统一表示为 $O(logN)$ ？

首先我们先复习对数换底公式:
$\log_{A}B=\frac{\log_{C}B}{\log_{C}A}$
则
$\log_{3}n=\frac{\log_{2}n}{\log_{2}3}=\frac{\log_{2}2}{\log_{2}3}\cdot\log_{2}n=\log_{3}2\cdot\log_{2}n$
所以 $O(\log_{3}n)=O(\log_{3}2\cdot\log_{2}n)$ ，因为 $\log_{3}2$ 为常数项，所以该项可以忽略，因此 $O(\log_{3}n)=O(\log_{2}n)$ ；所以无论对数以哪个数为底，最后都可以转化为一个常数项与以2为底的对数相乘，因此在对数阶时间复杂度的表示方法里，就忽略对数的底，统一表示为 $O(log N)$

$O(m+n)与O(m*n)$

此种表示形式的时间复杂度是由两个数据规模来决定的

public int accumulate(int m, int n) {
    int sum1 = 0;
    for (int i = 1; i <= m; i++) {
        sum1 += i;
    }

    int sum2 = 0;
    for (int i = 1; i <= n; i++) {
        sum2 += i;
    }

    return sum1 + sum2;
}

由于我们不能事先知晓m与n哪个量级大，所以就不能简单的利用加法规则取其最大量级，那么像这种代码的时间复杂度就为 $O(m+n)$ 。

public int accumulate(int m, int n) {
    int sum = 0;
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            sum += i * j;
        }
    }
    return sum;
}

而类似上述代码依然可以使用乘法法则，其时间复杂度为 $O(m*n)$

4，最好、最坏、平均和均摊时间复杂度

以下将通过一段代码来讲述这几个时间复杂度：

public class Test {
    private int[] array = new int[5];
    private int N = 0;

    public void push(int item) {
        if (N == array.length) {
            resize(2 * array.length);
        }
        array[N++] = item;
    }

    private void resize(int size) {
        int[] temp = new int[size];
        for (int i = 0; i < N; i++) {
            temp[i] = array[i];
        }
        array = temp;
    }
}

上述代码是用数组模拟一个栈的部分代码，其中push表示压栈操作，resize表示对数组进行扩容的操作；当压入栈中的元素数量达到数组的容量时，就定义一个容量为之前两倍的新数组temp，将旧数组array中的元素复制到新数组中，然后将array指向temp。

最好时间复杂度：最理想的情况下，当前栈中元素数量比数组的容量小，此时就直接执行代码块array[N++] = item;，即此时的时间复杂度为 $O(1)$ 。
最坏时间复杂度：最糟糕的情况下，当前栈中元素数量与数组的容量相等，此时就要执行resize方法进行扩容了，进入循环体，执行N次复制操作，此时的时间复杂度为 $O(N)$ 。
平均时间复杂度：
- 当栈中元素小于数组容量时，此时进行压栈就有N中情况，且每种情况的时间复杂度为 $O(1)$ ；当栈中元素与数组容量相等时，此时进行压栈就只有一种情况了，要进行扩容操作，这种情况的时间复杂度为 $O(N)$ ；则总共有N+1中情况，对其取平均值：
  $\cfrac{1+1+1+...+1+N}{N+1}=\cfrac{2N}{N+1}$
  在大 $O$ 标记法中，可以省略系数与低阶项，所以其平均时间复杂度为 $O(1)$
- 下面使用概率来分析，由于有N+1中情况，每种情况的发生概率为 $\frac{1}{N+1}$ ，则其平均时间复杂度为：
  $1\times\frac{1}{N+1}+1\times\frac{1}{N+1}+...+1\times\frac{1}{N+1}+N\times\frac{1}{N+1}=O(1)$
均摊时间复杂度：是一种特殊的平均时间复杂度，根据上述代码，每出现一次扩容操作时，即此时压栈的时间复杂度为 $O(N)$ ，那么后面的N次压栈操作的时间复杂度均为 $O(1)$ ，前后是连贯的，因此将 $O(N)$ 平摊到前N次上，得出均摊时间复杂度为 $O(1)$ 。

时间复杂度学习(上)

1，定义

2，时间复杂度分析

3，常见时间复杂度量级

4，最好、最坏、平均和均摊时间复杂度

猜你喜欢

热点阅读