关于时间复杂度和空间复杂度的理解

作者: MikeShine | 来源:发表于2019-04-01 14:34 被阅读0次

关于时间复杂度和空间复杂度的理解
时间复杂度和空间复杂度笔记
NLP初学之-算法复杂度
数据结构-0-时间复杂度和空间复杂度
排序算法的时间复杂度和空间复杂度
算法复杂度
算法复杂度之时间复杂度和空间复杂度
漫步数据结构与算法系列之时间复杂度
算法汇总
各种排序算法的时间与空间复杂度

做算法题，很重要的一点就是，需要分析算法的时间按复杂度和空间复杂度。
这里看一下对于时间复杂度和空间复杂度的理解

1. 时间复杂度（time complexity）

1.1 语句频度T(n)： 算法执行需要的时间，理论上只能通过上机来测试出来，但是我们不可能对所有的算法都来上机测试。我们只需要知道哪个算法用时比较多即可。一个算法花费的时间与算法中基本操作语句的执行次数成正比，哪个算法中语句执行次数多，哪个算法用时就长。而一个算法中语句执行的次数叫做语句频度，计作 T(n)。

总结一下，就是说我们用 T(n) 来算法执行的时间。

1.2 时间复杂度： 在T(n)中，n 叫做问题的规模，当 n 不断变化时，语句频度 T(n) 也会变化。我们想知道T(n) 的变化规律，于是便引入了时间复杂度的概念。
在衡量时间复杂度时候，我们通常用 O(x) 的概念。这里需要知道量级的概念：
如果
$\lim_{n \to \infty}{T(n)\over f(n)}=a \space\space\space这里的a代表非0常数$
这是时候，我们称作 f(n) 是 T(n) 同数量级函数，就计作 T(n)=O(f(n))，也就把 O(f(n)) 叫做算法的 渐进时间复杂度，简称 时间复杂度。
需要明白的是，语句频度T(n) 不同，时间复杂度也是可以相同的，直观理解就是说看最高次项。比如 T(n)=n^2+5n+6 和 T(n)=3n^2+n+3，时间复杂度都是 $O(n^2)$

1.3 常见时间复杂度： 常数阶 $O(1)$ ，对数阶 $O(log_2n)$ ，线性阶 $O(n)$ ，线性对数阶 $O(nlog_2n)$ ，平方阶 $O(n^2)$ ，立方阶 $O(n^3)$ ，k次方阶 $O(n^k)$ ，指数阶 $O(2^n)$ 。随着问题规模 n 的不断增大，上述时间复杂度不断增大，算法执行效率越低。

不同时间复杂度时间变化图

1.4 平均时间复杂度和最坏时间复杂度：
这里只需要明白，最坏时间复杂度是用来确定上界的。而且一般情况下，讨论的时间复杂度都是最坏时间复杂度。

1.5 如何求时间复杂度：
这里就每一种情况我们来给出例子和分析。

(1) 常数阶 $O(1)$ ----算法的执行时间不随着问题规模 n 的增长而增长。即使算法中有千万条语句，最终的执行时间也不过是一个较大的常数。

  public static void main(String[] args) {
        int x = 91;
        int y = 100;
        while (y > 0) {
            if (x > 100) {
                x = x - 10;
                y--;
            } else {
                x++;
            }
        }
    }

这段代码，总共循环了 1100次，但是可以看到，跟问题规模n没有关系。所以是一个常数阶的算法。

（2）对数阶 $O(log_2n)$ ---- 这里需要推导一下。

int i = 1, n = 100;
while(i < n){
 i = i * 2
}

假设这里的运行次数是T(n)， $由代码可知：2^{T(n)}=n$ ，则可以求出来 $T(n)=log_2n$ ，就是线性对数阶。

(3) 线性对数阶 $O(nlog_2n)$ ---- 这里的证明使用归纳法

快排代码

可以看到，快排就是线性对数阶的时间复杂度。除此之外，还有归并排序和堆排序。

（4）线性阶 $O(n)$ -----就是单层循环。

for(int i=0;i<nums.lengt;i++){
    nums[i]++;  
}

(5) 平方阶 $O(n^2)$ ------ 就是双层循环

for(int i=0;i<nums.lengt;i++){
    for(int j=i+1;j<nums.lengt;j++){
      nums[i] = nums[j];
}

(6) 立方阶 $O(n^3)$ ------ 就是三层循环

同上

(7) k次方阶 $O(n^k)$ ------ k层循环

同上

(8) 指数阶 $O(2^n)$ ------

2. 空间复杂度（space complexity）

空间复杂度，是说程序运行时临时占用的空间的大小。同上面说过的时间复杂度，计作 $S(n)=O(f(n))$ 。
一个算法除了需要存储本事所使用的指令、常数、变量和输入数据外，还需要一些对数据进行操作的工作单元和存储一些计算所需的辅助空间。总的来说，算法执行时所需的存储空间包括以下两个部分。

固定部分------这部分空间的大小与输入/输出的数据个数、数值无关。主要包括指令空间（代码空间）、数据空间（常量、简单变量）等所占的空间。属于静态空间。
可变空间------主要包括动态分配的空间，以及递归栈所需的空间等。这部分空间大小与算法有关。
举一个栗子

public void reserse(int[] a, int[] b) {
        int n = a.length;
        for (int i = 0; i < n; i++) {
            b[i] = a[n - 1 - i];
        }
    }

这部分代码中，函数 reverse() 运行时，要分配的内存空间包括：引用a、引用b、局部变量n、局部变量i。
因此有 $f(n)=4$ ，所以有空间复杂度 $S(n)=O(1)$