算法的时间与空间复杂度

算法的时间与空间复杂度

看到群里们小伙伴在讨论算法复杂度问题，之前在极客时间看了王争的《数据结构与算法之美》，看的我也晕呼呼的，跟上学时在学校老师的讲的有点不一样了，网上搜了下各种各样的，结合参考作一篇简单易懂的总结。

什么是算法

算法是解决特定问题求解步骤的描述，在计算机中表现为指令的有限序列，并且每条指令表示一个或多个操作。

如何评价一个算法的好坏

一般我们会从以下维度来评估算法的优劣

1. 正确性（废话）
2. 可读性
3. 健壮性（对不合理输入的反应能力和处理能力），如下面代码n <= 0
4. 时间复杂度 ：估算程序指令的执行次数 （执行时间）
5. 空间复杂度 ：估算所需占用的存储空间

// 计算1+2+3+4+...+n的和

function sum1(n) {
    let result = 0
  for(let i = 0 ; i <= n; i++) {
      resutl += i
  }
  return result
}

function sum2(n) {
    return (1 + n) * n / 2
}

时间复杂度

概念

对于一个给定的算法，除了要确定它的准确性外，还要分析算法的时间复杂度。算法的时间复杂度反映了程序执行时间随输入规模增长而增长的量级，很大程度上决定了算法的优劣。

程序执行时间的计算，有两种方式：

• 事后统计法 不是一个好方法，原因：需要大规模的实际运行，而且运行时间也跟运行环境，机器等因素有关，不能很好反应算法的运行时间。

• 事前分析估算法 在编写程序前，依据统计方法对算法进行估算。一个用高级语言编写的程序在计算机上运行时所消耗的时间取决于下列因素：

  • 算法采用的策略、方法；
  • 编译产生的代码质量；
  • 问题的输入规模；
  • 机器执行指令的速度。

大O符号表示法

一般情况下，算法的基本操作重复执行的次数是模块 n 的某一函数 f(n) ，因此，算法的时间复杂度记作：T(n) = O(f(n))，即 「 大O符号表示法 」

随着模块n的增大，算法执行的时间增长率f(n)的增长率成正比，所以f(n)越小，算法的时间复杂度越低，算法的效率越高。

时间复杂度是总运算次数表达式中受n的变化影响最大的那一项(不含系数)

举个简单的例子：

int value = 0;                    // 执行了1次
for (int i = 0; i < n; i++) {     // 执行了n次
    value += i;
}

这个算法执行了 1 + n 次，如果n无限大，我们可以把前边的1忽略，也就是说这个算法执行了n次。

时间复杂度常用大O符号表示，这个算法的时间复杂度就是O(n)。

用 O(n) 来体现算法时间复杂度的记法被称作 大O表示法 。 一般我们我们评估一个算法都是直接评估它的最坏的复杂度。

大O表示法 O(f(n)) 中的 f(n) 的值可以为 1、n、logn、n^2 等 所以我们将：O(1)、O(n)、O(logn)、O( n^2 )分别称为常数阶、线性阶、对数阶和平方阶。

推导大O阶几种规则

忽略常数、系数、低阶

1. 常数省略，若 T(n) 本身就为常数，则 f(n) = 1
2. 低次阶省略，只保留最高阶项，例如 T(n) = n^3+n^2+3 ，则 f(n) = n^3
3. 系数忽略，例如 T(n) = 3n^3+n^2+3 ，则 f(n)= n^3
4. 对数底数忽略，例如 T(n) = log2n , 则 f(n) = logn ，这里不写底数，表示任何底数都可包含

9                                >> O(1)
2n + 3                       >> O(n)
n^2 + 2n + 6             >> O(n^2)
4n^3 + 3n^2 ++ 22n + 100 >> O(n^3)

示例：

public static void test2(int n) {
        // O(n)
        // 1 + 3n
        for (int i = 0; i < n; i++) { // i = 0 1次; i<n n次; i++ n次
            System.out.println("test"); // n次
        }
    }

    public static void test3(int n) {
        // 1 + 2n + n * (1 + 3n)
        // 1 + 2n + n + 3n^2
        // 3n^2 + 3n + 1
        // O(n^2)

        // O(n)
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                System.out.println("test");
            }
        }
    }

    public static void test4(int n) {
        // 1 + 2n + n * (1 + 45)
        // 1 + 2n + 46n
        // 48n + 1
        // O(n)
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < 15; j++) { // j<15 15次; j++ 15次
                System.out.println("test");  // 15次
            }
        }
    }

    public static void test5(int n) {
        // 8 = 2^3
        // 16 = 2^4

        // 3 = log2(8)
        // 4 = log2(16)

        // 执行次数 = log2(n)
        // O(logn)
        while ((n = n / 2) > 0) {
            System.out.println("test");
        }
    }

    public static void test6(int n) {
        // log5(n)
        // O(logn)
        while ((n = n / 5) > 0) {
            System.out.println("test");
        }
    }

    public static void test7(int n) {
        // 1 + 2*log2(n) + log2(n) * (1 + 3n)

        // 1 + 3*log2(n) + 2 * nlog2(n)
        // O(nlogn)
        for (int i = 1; i < n; i = i * 2) {
            // 1 + 3n
            for (int j = 0; j < n; j++) {
                System.out.println("test");
            }
        }
    }

    public static void test10(int n) {
        // O(n)
        int a = 10;
        int b = 20;
        int c = a + b;
        int[] array = new int[n];
        for (int i = 0; i < array.length; i++) {
            System.out.println(array[i] + c);
        }
    }

时间复杂度的计算

常见的时间复杂度量级有：

• 常数阶O(1)
• 线性阶O(n)
• 对数阶O(logN)
• 线性对数阶O(nlogN)
• 平方阶O(n²)
• 立方阶O(n³)
• K次方阶O(n^k)
• 指数阶(2^n)

常数阶O(1)

无论代码执行了多少行，只要是没有循环等复杂结构，那这个代码的时间复杂度就都是 O(1)，如：

function test() {
  let sum = 0, n = 10;               // 语句执行1次 
  let sum = (1+n)*n/2;                        // 语句执行1次 
  console.log(`The sum is : ${sum}`) // 语句执行1次 
}

上述代码在执行的时候，它消耗的时候并不随着某个变量的增长而增长，那么无论这类代码有多长，即使有几万几十万行，都可以用 O(1) 来表示它的时间复杂度。

线性阶O(n)

线性阶的循环结构会复杂很多。要确定某个算法的阶次，我们常常需要确定某个特定的语句或某个语句集运行的次数。因此，我们要分析算法的复杂度，关键就是要分析循环结构的运行情况。

let i =0;                           // 语句执行一次 
while (i < n) {                     // 语句执行n次 
  console.log(`Current i is ${i}`); //语句执行n次
  i++;                              // 语句执行n次
}

这个算法中代码总共执行了 3n + 1次，根据规则 1->2（常数省略 ，低次阶省略，只保留最高阶项），因此该算法的时间复杂度是O(n)。

对数阶O(logN)

对数是求指数的运算，比如 log2x 的意思就是求x是2的多少次幂。

let i = 1;          // 语句执行一次 
while (i < n) {     // 语句执行logn次
  i = i * 2;        // 语句执行logn次 log2(n)
}

从上面代码可以看到，在while循环里面，每次都将 i 乘以 2，乘完之后，i 距离 n 就越来越近了。 假设循环x次之后，i 就大于 2 了，此时这个循环就退出了。 也就是说 2 的 x 次方等于 n，那么 x = log2^n。 所以整段代码执行次数为1 + 2*logn，则f(n) = logn，时间复杂度为O(logn)。

线性对数阶O(nlogN)

线性对数阶O(nlogN) 其实非常容易理解，将时间复杂度为 O(logn) 的代码循环 N 遍的话，那么它的时间复杂度就是 n * O(logN) ，也就是了 O(nlogN) 。

上面的代码加一点修改来举例：

for(m=1; m<n; m++)
{
    i = 1;
    while(i<n)
    {
        i = i * 2;
    }
}

for 循环内部的代码执行次数为：1 + 2logn，则复杂为度为：O(logn)。 循环执行m次，即： m O(logn)，则复杂度为 O(nlogN) 。

平方阶O(n²)

平方阶O(n²) 就更容易理解了，如果把 O(n) 的代码再嵌套循环一遍，它的时间复杂度就是 O(n²) 了。 举例：

for(x=1; i<=n; x++)
{
   for(i=1; i<=n; i++)
    {
       j = i;
       j++;
    }
}

这段代码其实就是 嵌套了2层n循环，它的时间复杂度就是 O(n*n)，即 O(n²)

如果将其中一层循环的n改成m，即：

for(x=1; i<=m; x++)
{
   for(i=1; i<=n; i++)
    {
       j = i;
       j++;
    }
}

那它的时间复杂度就变成了 O(mn) *

立方阶O(n³)、K次方阶O(n^k)

参考上面的O(n²) 去理解就好了，O(n³)相当于三层n循环，其它的类似。

常见的时间复杂度

常见的算法时间复杂度由小到大排列如下：

空间复杂度

一个算法的空间复杂度S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。 渐近空间复杂度也常常简称为空间复杂度。

空间复杂度是对一个算法在运行过程中临时占用的存储空间大小的度量。

一个算法在执行过程中所需要的存储空间包括以下3个部分：

1. 算法本身占用的空间，取决于算法的长度；
2. 输入输出数据占用的空间，取决于问题规模，与算法无关；
3. 辅助存储空间，即算法临时开辟的存储空间，与算法有关。

算法的空间复杂度也用 O 表示，指的是该算法所占用的空间随问题规模n的增长所变化的情况。

• O(1) 表示算法所占用空间不随n的增长而增长
• O(n) 表示算法所占用空间随n的增长线性增长

在衡量一个算法的效率时，主要考虑时间复杂度，因为时间复杂度直接与用户体验相关，用空间换取时间也是可行的。

参考

• 《图解算法》
• 《大话数据结构》
• 算法的时间复杂度和空间复杂度
• 算法的时间复杂度和空间复杂度总结
• 算法的时间复杂度和空间复杂度
• 算法的时间复杂度和空间复杂度