【初阶数据结构篇】时间（空间）复杂度

正文

算法

​ 算法(Algorithm):就是定义良好的计算过程，他取⼀个或⼀组的值为输⼊，并产⽣出⼀个或⼀组值作为输出。简单来说算法就是⼀系列的计算步骤，⽤来将输⼊数据转化成输出结果。

​ 程序=数据结构+算法，一个好的程序需要有一个好的算法，那如何去衡量一种算法的好坏呢？这就需要我们计算算法的复杂度。

复杂度

​ 复杂度是计算机科学中的一个基础概念，它帮助我们理解和评估算法的效率，对于算法设计和优化至关重要。算法的复杂度通常分为时间和空间复杂度两个方面。

时间复杂度

---

1. 定义

​ 在计算机科学中，算法的时间复杂度是⼀个函数式T(N)，它定量描述了该算法的运⾏时间。时间复杂度是衡量程序的时间效率，那么为什么不去计算程序的运⾏时间呢？

​ 1.因为程序运⾏时间和编译环境和运⾏机器的配置都有关系，⽐如同⼀个算法程序，⽤⼀个⽼编译器进⾏编译和新编译器编译，在同样机器下运⾏时间不同。

​ 2.同⼀个算法程序，⽤⼀个⽼低配置机器和新⾼配置机器，运⾏时间也不同。

​ 3.并且时间只能程序写好后测试，不能写程序前通过理论思想计算评估。

---

2. 表示方法

​ 如定义所示，时间复杂度是一个函数式T(N)，T(N)通过表示程序的指令的执行次数来定量描述程序的运行时间。

​ 例如，T(N)=10，T(N)=2N+10，T(N)=N²等等等，都是描述一个程序指令的执行次数

​ 但是，设想一下，采用这样的表示方法，如果两种算法一种T(N)=N²，另一种T(N)=N²+100，当N越大时二者差距就可以忽略不计，如果我们仍然这样表示，不免缺乏简洁性和统一性。

大O渐进表示法

​ 在这基础上，我们联想数学中所学的等阶无穷大概念，数学中使用小o来表示高阶无穷小，而采用大O来表示等阶无穷大。具体的来说，对于函数T(N)，当N趋于无穷时，我们能否找到这样一个函数f(N)，使得$\frac{T(N)}{f(N)}$为一个常数，答案是可以的。

---

3. 常见时间复杂度

下面列出了一些常见时间复杂度O(N)的表示法，即f(N)的常见形式。

• 常数时间复杂度：O(1)，表示算法的执行时间不随输入规模的增长而变化，是最理想的情况。
• 对数时间复杂度：O(log n)，通常出现在二分查找等分治算法中。
• 线性时间复杂度：O(n)，表示算法的执行时间与输入规模成正比。
• 线性对数时间复杂度：O(n log n)，通常出现在快速排序、归并排序等分治算法中。
• 平方时间复杂度：O(n²)，通常出现在嵌套循环的算法中。
• 指数时间复杂度：O(2ⁿ)，通常出现在递归算法中。
• 多项式时间复杂度：O(n^k)，k可能是大于 2 的正整数，这意味着算法在大规模数据上的性能下降较快。

---

4.案例计算分析

冒泡排序

// 计算BubbleSort的时间复杂度？
void BubbleSort(int* a, int n)
{
     assert(a);
      for (size_t end = n; end > 0; --end)
     {
         int exchange = 0;
     for (size_t i = 1; i < end; ++i)
         {
             if (a[i-1] > a[i])
             {
             Swap(&a[i-1], &a[i]);
             exchange = 1;
             }
         }
     if (exchange == 0)
     break;
     }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

• 最好情况，若数组有序

​ T(N) =N

• 最差情况，若数组与要求顺序反序

​ T(N) =$\frac{N\ast (N-1)}{2}$

​ 有n个元素，需要排n-1趟，第i趟需要排n-i次

即(n-1)+(n-2)+……+1，结果如上所示

我们发现上述第一种是最好情况，而第二种是最坏情况，俗话说的好“做最好的准备，做最坏的打算”，所以很合理的我们应该将最坏的情况计算结果当做时间复杂度，上述即T[N]=N²。

---

二分查找

// 计算BinarySearch的时间复杂度？
int BinarySearch(int* a, int n, int x)
{
    assert(a);
 
    int begin = 0;
    int end = n - 1;
    while (begin < end)
    {
        int mid = begin + ((end - begin) >> 1);
        if (a[mid] < x)
            begin = mid + 1;
        else if (a[mid] > x)
            end = mid;
        else
            return mid;
    }
 
    return -1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

• 最好情况

  O(1)

• 最坏情况

  O(logN)

  一次对半筛选，当数据很多时筛选k次才找到，2^k=N，对数函数增长规律一样，为了保持统一性，下标可以忽略，建议写法即为logN。

---

斐波那契数列（递归法）

// 计算斐波那契递归Fib的时间复杂度？
long long Fib(size_t N)
{
    if (N < 3)
        return 1;
 
    return Fib(N - 1) + Fib(N - 2);
}
1
2
3
4
5
6
7
8

以此类推，即为O(2^N)。

斐波那契数列（迭代法）

long long  Fib(size_t n)
{
	int a = 1;
	int b = 1;
	int c = 1;
	while (n > 2)
	{
		c = a + b;
		a = b;
		b = c;
		n--;
	}
	return c;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

• 可见我们使用迭代的方法，将时间复杂度降为了O(N)。

---

空间复杂度

类比时间复杂度，相似内容不再过多赘述了

• 空间复杂度也是⼀个数学表达式，是对⼀个算法在运⾏过程中因为算法的需要额外临时开辟的空间。

• 空间复杂度不是程序占⽤了多少bytes的空间，因为常规情况每个对象⼤⼩差异不会很⼤，所以空间复杂度算的是变量的个数。

• 注意：函数运⾏时所需要的栈空间(存储参数、局部变量、⼀些寄存器信息等)在编译期间已经确定好了，因此空间复杂度主要通过函数在运⾏时候显式申请的额外空间来确定!

---

案例分析

下面我们用具体案例来熟悉空间复杂度的计算

冒泡排序

// 计算BubbleSort的时间复杂度？
void BubbleSort(int* a, int n)
{
     assert(a);
      for (size_t end = n; end > 0; --end)
     {
         int exchange = 0;
     for (size_t i = 1; i < end; ++i)
         {
             if (a[i-1] > a[i])
             {
             Swap(&a[i-1], &a[i]);
             exchange = 1;
             }
         }
     if (exchange == 0)
     break;
     }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

• 我们只申请了常数个变量，所以很显然空间复杂度为O(1)

---

斐波那契数列（递归法）

// 计算斐波那契递归Fib的时间复杂度？
long long Fib(size_t N)
{
    if (N < 3)
        return 1;
 
    return Fib(N - 1) + Fib(N - 2);
}
1
2
3
4
5
6
7
8

• 空间复杂度为O(N)
• 当我们输入N时，第一步递归将会沿着N-1，N-2一直到3递推，在n为3这个函数栈帧里调用2和1，并返回给3注意此时1和2的函数栈帧已经销毁，以此类推，返回一个销毁一个，程序在执行时同一时刻实际使用的空间不会超过n个(即往下递推的深度),只是每个n值相同函数栈帧在不同时刻执行了一次又一次的销毁创建过程，即在时间复杂度里面我们所讨论的调用次数的问题，但在空间复杂度中我们只关心使用的空间，故为O(N)。

---

斐波那契数列(迭代法)

long long  Fib(size_t n)
{
	int a = 1;
	int b = 1;
	int c = 1;
	while (n > 2)
	{
		c = a + b;
		a = b;
		b = c;
		n--;
	}
	return c;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

• 这个也很显而易见了，为O(1)。

---

时间复杂度对比

下面是常见时间复杂度对比

​