时间复杂度和空间复杂度

一.时间复杂度

1.1 什么是时间复杂度

时间复杂度计算的是程序运行所花费的时间。但是，同一个程序在不同电脑上运行的时间也是不同的，因为不同电脑的性能不同。所以，一般说时间复杂度并不是真正的代码运行的时间，而是一个程序中代码所运行的次数。将这个次数写成一个数学函数表达式，这个表达式就是此程序的时间复杂度。

1.2 大O渐进表示法

1.2.1 大O表示法的规则

• 仅保留最高次数项。
• 最高项的系数为 1。
• 当代码的运行次数为常数时，统一记为 O(1)。
• 对数阶的时间复杂度不管是以几为底，通常都将对数的底数忽略，也就是都记为 O(logn)。

常见的渐进时间复杂度大小顺序为：

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2^n) < O(n!) < O(n^n)

1.2.2 示例解释

1.O(n)

#include 
using namespace std;
int main()
{
 int n;  // 运行次数为1
    cin >> n;  // 运行次数为1
 
 for(int i=0; i < n; i ++)
    {
 printf("%d ", i); // 运行次数为n
    }
 
 int m = 10;  // 运行次数为1
 
 while(m --)
    {
 printf("Hello World\n");  // 运行次数为10
    }
 
 return 0;
}

整个程序的运行次数为 n + 13，运行次数的函数表达式为 F(n) = n + 13，大 O 表示法记作 O(n)。

2.O(n^2)

void Func(int n)
{
 int count = 0;  // 执行次数为1
 
 for(int i =0; i < n; i++)  // 总执行次数为n*n
    {
 for(int j = 0; j < n;j++)
        {
            count ++;
        }
    }
 
 for(int k = 0; k < 2 * n; k++)  // 执行次数为2n
    {
        count ++;
    }
 
 int m = 10;  // 执行次数为1
 
 while(m --)  // 执行次数为10
    {
        count ++;
    }
 
    cout << count << endl;  // 执行次数为1
}

整个程序的运行次数为 n*n + 2*n + 13，运行次数函数表达式为 F(n) = n*n + 2*n + 13，大 O 表示法记作 O(n^2)。

假设，n = 10，n = 100，n = 1000 ...... 时：

n = 10 时，F(n)=133；

n = 100 时，F(n) = 10213;

n = 1000 时，F(n) = 1002013;

......

随着 n 的增大，n*n 的占比越大，剩余项可以完全忽略，只需要保留该函数表达式中的最高次项。

上述程序的运行次数函数表达式可以简化为 O(n^2)。

1.2.3 最坏情况、最好情况、平均情况

有时，算法运行的次数是不确定的。例如，利用遍历方式在长度为 n 的数组中找一个数字。

分为以下几种情况：

• 最好的情况，我们要找的数字正好是数组第一个元素，此时算法的时间复杂度为 O(1)。
• 最坏的情况，我们要找的数字正好是数组的最后一个元素，此时算法的时间复杂度为 O(n)。
• 在最好和最坏情况间取平均值，即 n/2，利用大 O 表示法时，省略最高项系数，时间复杂度仍为 O(n)。

所以，算法的时间复杂度可分为三种情况

• 最坏情况：任意输入规模的最大运行次数（上界）；
• 平均情况：任意输入规模的期望运行次数；
• 最好情况：任意输入规模的最小运行次数（下界）； 

1.3 常见的时间复杂度分析

1.O(1)

void f(int n)
{
    int count = 0;
    for (int k = 0; k < 100; ++ k)
    {
        count ++;
    }
    printf("%d\n", count);
}

2.O(n)

void f(int n)
{
    int count = 0;
    for (int k = 0; k < 2 * n; ++ k)
    {
        count ++;
    }
 
    int m = 10;
    while (m --)
    {
        count ++;
    }
    printf("%d\n", count);
}

3.O(log n)

不管是以几为底，把所有对数阶的时间复杂度都记为 O(logn)。

在算法分析中，我们通常将对数的底数忽略，因为对于渐进式增长来说，不同对数底数之间的差异是可以忽略的。这是因为我们主要关注算法的增速和趋势，而不是具体的常数因子或底数。因此，当我们说一个算法的时间复杂度是对数阶时，通常表示为 O(log n)，而不考虑底数。无论是以2为底、以10为底、还是以其他任何常数为底，对数增长的趋势都是相同的。

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

4.O(m + n)

m 和 n 表示两个数据规模。

void f(int n, int m)
{
    int count = 0;
    for (int k = 0; k < m; ++ k)
    {
        count ++;
    }
    for (int k = 0; k < n; ++ k)
    {
        count ++;
    }
    printf("%d\n", count);
}

二.空间复杂度

在计算机发展初期，计算机的存储容量很小，所以对空间复杂度很是在乎。但是经过这几十年计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。

2.1 空间复杂度案例

先来看一个例子，现在有一个算法是这样的，给定一个数组，将数组中每个元素都乘以2返回，我实现了下面两种形式：

private static int[] multi1(int[] array) {
    int[] newArray = new int[array.length];
    for (int i = 0; i < array.length; i++) {
        newArray[i] = array[i] * 2;
    }
    return newArray;
}
 
private static int[] multi2(int[] array) {
    for (int i = 0; i < array.length; i++) {
        array[i] = array[i] * 2;
    }
    return array;
}

暂且不论这两个算法孰好孰坏，你来猜猜他们的空间复杂度各是多少？

你可能会说第一个算法的空间复杂度为O(n)，第二个算法的空间复杂度为O(1)。

错！两个算法的空间复杂度都是O(n)。也不能说你完全错了，因为大部分书籍或者资料都弄错了。

是时候了解真正的空间复杂度了。

2.1 什么是空间复杂度

空间复杂度，是指一个算法运行的过程占用的空间，这个空间包括输入参数的占用空间和额外申请的空间。

所以，针对上面两个算法：

• 第一个算法，输入参数n，额外空间n，两者相加为2n，去除常数项，空间复杂度为O(n)；
• 第二个算法，输入参数n，额外空间0，两者相加为n，空间复杂度为O(n)。

可以看到，使用空间复杂度很难判断这两个算法的好坏，所以，诞生了另一个概念：额外时间复杂度。

2.2 什么是额外空间复杂度

额外空间复杂度：是指一个算法运行过程中额外申请的空间。

使用额外空间复杂度，针对上面两个算法：

• 第一个算法，额外空间为n，额外空间复杂度为O(n)；
• 第二个算法，额外空间为0，额外空间复杂度为O(1)；

可以看到，从空间占用的角度，使用额外空间复杂度能够很轻易地判断两个算法的好坏。所以，是时候纠正错误的概念了，以后与人交流的时候最好使用“额外空间复杂度”这个概念，但是刷题的时候的要求是空间复杂度，那还是要使用空间复杂度的概念。