C语言【数据结构】：时间复杂度和空间复杂度.详解

引言

        详细介绍什么是时间复杂度和空间复杂度。

前言：为什么要学习时间复杂度和空间复杂度

        算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。

        时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量⼀个算法运行所需要的额外空间。 在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注⼀个算法的空间复杂度。

一、时间复杂度 

问：时间复杂度是程序运行的时间吗？                     

        这是一个很严重的问题。这里先肯定回答：不是。

仔细往下看，最后你亲自来回答这个问题                                

1.什么是时间复杂度

        时间复杂度是对一个算法运行时间长短的一种度量，它描述的是随着输入数据规模 n 的增大，算法执行时间的增长趋势，而不是具体的运行时间。因为具体运行时间会受到硬件、编程语言、编译器等多种因素的影响，所以使用时间复杂度可以更客观地评估算法的效率。

    

程序执行的时间  =  二进制指令运行的时间 * 执行的次数 

        因为程序在计算机中二进制指令的运行时间是非常快的，可以假定时间是一样的，所以使用代码的执行次数来等效程序的执行时间 

2.表示方法（大O表示法）

        通常使用大 O 符号（Big O notation）来表示时间复杂度。大 O 符号表示的是算法执行时间的上界，即最坏情况下的时间复杂度。看到这里你可能不知道什么是大O表示法，跟随下面的案例来理解，就明白什么是大O表示法了。

        推导大O阶规则

        1. 时间复杂度函数式 T(N) 中，只保留最高阶项，去掉那些低阶项，因为当 N 不断变⼤时， 低阶项对结果影响越来越⼩，当 N 无穷大时，就可以忽略不计了。

         2. 如果最高阶项存在且不是 1 ，则去除这个项目的常数系数，因为当 N 不断变大，这个系数对结果影响越来越小，当 N 无穷大时，就可以忽略不计了。

         3.T(N) 中如果没有 N 相关的项目，只有常数项，用常数 1 取代所有加法常数。

3.常见的时间复杂度

1. O(1)：常数时间复杂度

代码一：

        推导一下这段代码的执行次数T与n之间的函数关系

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

        T（N）= 2 * N + 10；

当N足够大时，从1 增长到10000000，会发现2 和10 对次数的影响不是很大，所以

        1. 如果最高阶项存在且不是 1 ，则去除这个项目的常数系数，因为当 N 不断变大，这个系数对结果影响越来越小，当 N 无穷大时，就可以忽略不计了。

        2. T(N) 中如果没有 N 相关的项目，只有常数项，用常数 1 取代所有加法常数。

代码二： 

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

        观察这段代码，会发现n和程序的执行次数是没有关系的（T（N）= 100），这时就认为时间复杂度为O（1）；

2. O(n)：线性时间复杂度

代码一：

        算法的执行时间与输入数据规模 n 成正比。

#include <stdio.h>// 计算数组元素的和
int sum(int arr[], int n) {int total = 0;for (int i = 0; i < n; i++) {total += arr[i];}return total;
}int main() {int arr[] = {1, 2, 3, 4, 5};int n = sizeof(arr) / sizeof(arr[0]);int result = sum(arr, n);printf("Sum = %d\n", result);return 0;
}

        在 sum 函数中，需要遍历数组中的每个元素，因此循环的执行次数与数组的长度 n 成正比，时间复杂度为 O(n)。即因为是要循环n次，所以是O(n)。

代码二： 

const char* strchr(const char* str, int character)
{const char* p_begin = 's';while (*p_begin != character){if (*p_begin == '\0')return NULL;p_begin++;}return p_begin;

 strchr执行的基本操作次数：

1）若要查找的字符在字符串第⼀个位置，则： T(N) = 1

2）若要查找的字符在字符串最后的⼀个位置， 则： T(N) = N

3）若要查找的字符在字符串中间位置，则：N T(N) = 2 因此：strchr的时间复杂度分为： 最好情况： O(1)

最坏情况： O(N)

平均情况： O(N)

通过上面我们会发现，有些算法的时间复杂度存在最好、平均和最坏情况。

最坏情况：任意输入规模的最大运行次数(上界)

平均情况：任意输入规模的期望运行次数

最好情况：任意输入规模的最小运行次数(下界)

大O的渐进表示法在实际中⼀般情况关注的是算法的上界，也就是最坏运行情况。

所以上面这段代码的时间复杂度是O（N）

3. O(n^2)：平方时间复杂度

        算法的执行时间与输入数据规模 n 的平方成正比。

参考代码：

#include <stdio.h>// 冒泡排序
void bubbleSort(int arr[], int n) {for (int i = 0; i < n - 1; i++) {for (int j = 0; j < n - i - 1; j++) {if (arr[j] > arr[j + 1]) {int temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}int main() {int arr[] = {64, 34, 25, 12, 22, 11, 90};int n = sizeof(arr) / sizeof(arr[0]);bubbleSort(arr, n);for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");return 0;
}

粗略理解：在 bubbleSort 函数中，使用了两层嵌套循环，因此时间复杂度为 O(n^2)。

细节分析：

        1）若数组有序，则： T(N)=N

        2）若数组有序且为降序，则： T(N)=  1 + 2 + 3 + .......+ n - 1 = ((n - 1) * (1 + n - 1) ) / 2   即等差数列求和公式：a1 = 1， an = n - 1, 共n - 1项。

        T（N）= (n^2) * 1 / 2 + n / 2;

       因此：BubbleSort的时间复杂度取最差情况为： O(N ^ 2)

4. O(log n )：复杂度

参考代码：

void func5(int n)
{int cnt = 1;while (cnt < n){cnt *= 2;}
}

当n= 2 时，执行次数为1

当n= 4 时，执行次数为2

当n=16时，执行次数为4

假设执行次数为x，则 2^x = x  因此执行次数： x=logn

因此：func5的时间复杂度取最差情况为：O(log n) 

这里为什么不写

因为这个在输入法上不好打出来

注意：在有的地方会把  logn  写成lgn，严格上来说这个是不对的

        当n接近无穷大时，底数的大小对结果影响不大。因此，一般情况下不管底数是多少都可以省略不写。

还有其他的时间复杂度如：n*logn, n!(n的阶乘)，在以后的学习中肯定会遇到

二、空间复杂度

 1.什么是空间复杂度

定义

        空间复杂度是对一个算法在运行过程中临时占用存储空间大小的一种度量，它描述的是随着输入数据规模 n 的增大，算法所需额外存储空间的增长趋势。

注意：函数栈帧的创建和销毁是不算入空间复杂度的，即 创建函数 和 销毁函数 是不算入时间复杂度的。

表示方法

        同样使用大 O 符号来表示空间复杂度。

常见的空间复杂度及其示例代码

1. O(1)：常数空间复杂度

算法在运行过程中所需的额外存储空间是固定的，不随输入数据规模 n 的变化而变化。

#include <stdio.h>// 计算数组元素的和
int sum(int arr[], int n) {int total = 0;for (int i = 0; i < n; i++) {total += arr[i];}return total;
}int main() {int arr[] = {1, 2, 3, 4, 5};int n = sizeof(arr) / sizeof(arr[0]);int result = sum(arr, n);printf("Sum = %d\n", result);return 0;
}

        在 sum 函数中，只使用了一个额外的变量 total 来存储数组元素的和，因此空间复杂度为 O(1)。

2. O(n)：线性空间复杂度

算法在运行过程中所需的额外存储空间与输入数据规模 n 成正比。

#include <stdio.h>
#include <stdlib.h>// 复制数组
int* copyArray(int arr[], int n) {int *newArr = (int*)malloc(n * sizeof(int));for (int i = 0; i < n; i++) {newArr[i] = arr[i];}return newArr;
}int main() {int arr[] = {1, 2, 3, 4, 5};int n = sizeof(arr) / sizeof(arr[0]);int *newArr = copyArray(arr, n);for (int i = 0; i < n; i++) {printf("%d ", newArr[i]);}printf("\n");free(newArr);return 0;
}

在copyArray 函数中，使用了 malloc 函数动态分配了一个大小为 n 的数组，因此空间复杂度为 O(n)。 

5. 常见复杂度对比

  

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

        但是，在算法竞赛中，往往需要有一种思想：用时间换空间，或者用空间换时间。