数据结构之算法复杂度

---

前言

        本文主要讲述数据结构中的算法复杂度

---

一、复杂度的概念

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

• 时间复杂度主要衡量一个算法的运行快慢。
• 空间复杂度主要衡量一个算法运行所需要的额外空间。

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

---

二、时间复杂度

在计算机科学中，算法的时间复杂度是一个函数式T(N)，它定量描述了该算法的运行时间。时间复杂度是衡量程序的时间效率。

那么为什么不去计算程序的运行时间呢？

1. 因为程序运行时间和编译环境和运行机器的配置都有关系，比如同一个算法程序，用⼀个老编译器进行编译和新编译器编译，在同样机器下运行时间不同。
2. 同一个算法程序，用⼀个老低配置机器和新高配置机器，运行时间也不同。
3. 并且时间只能程序写好后测试，不能写程序前通过理论思想计算评估。

那么算法的时间复杂度是一个函数式T(N)，到底是什么呢？

答：这个T(N)函数式计算了程序的执行次数。

通过c语言编译链接章节学习，我们知道算法程序被编译后生成二进制指令，程序运行，就是cpu执行这些编译好的指令。那么我们通过程序代码或者理论思想计算出程序的执行次数的函数式T(N)，假设每句指令执行时间基本一样(实际中有差别，但是微乎其微)，那么执行次数和运行时间就是等比正相关， 这样也脱离了具体的编译运行环境。执行次数就可以代表程序时间效率的优劣。比如解决一个问题的算法a程序T(N)=N，算法b程序T(N)=N^2，那么算法a的效率⼀定优于算法b。

示例：

//请计算⼀下Func1中++count语句总共执行了多少次？void Func1(int N)
{int count = 0;for (int i = 0; i < N; ++i){for (int j = 0; j < N; ++j){++count;}}for (int k = 0; k < 2 * N; ++k){++count;}int M = 10;while (M--){++count;}
}

画图表示：

解析：实际中我们计算时间复杂度时，计算的也不是程序的精确的执行次数，精确执行次数计算起来还是很麻烦的(不同的⼀句程序代码，编译出的指令条数都是不⼀样的)，计算出精确的执行次数意义也不大， 因为我们计算时间复杂度只是想比较算法程序的增长量级，也就是当N不断变大时T(N)的差别，上面我们已经看到了当N不断变大时常数和低阶项对结果的影响很小，所以我们只需要计算程序能代表增长量级的大概执行次数，复杂度的表示通常使用大O的渐进表示法。

---

三、大O的渐进表示法

大O符号（BigOnotation）：是用于描述函数渐进行为的数学符号

推导大O阶规则：

1. 时间复杂度函数式 T(N) 中，只保留最高阶项，去掉那些低阶项，因为当 N 不断变大时， 低阶项对结果影响越来越小，当 N 无穷大时，就可以忽略不计了。
2. 如果最高阶项存在且不是 1 ，则去除这个项目的常数系数，因为当 N 不断变大，这个系数对结果影响越来越小，当 N 无穷大时，就可以忽略不计了。
3. T(N) 中如果没有 N 相关的项目，只有常数项，用常数 1 取代所有加法常数。

通过大O渐进表示法，我们可以推出上述 Func1 的时间复杂度了：（因为主要是++count的运行次数，所以时间复杂度也是主要计算它的运行次数）

 

示例1：

//计算Func2的时间复杂度？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);
}

画图表示：

---

示例2：

//计算Func3的时间复杂度？void Func3(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);
}

画面表示：

解释：如果M>>N，则时间复杂度可以为O(M)，反之N>>M，则时间复杂度可以写成O(N)，如果M==N，则时间复杂度为O(M+N)

---

示例3：

//计算Func4的时间复杂度？void Func4(int N)
{int count = 0;for (int k = 0; k < 100; ++k){++count;}printf("%d\n", count);
}

画图表示：

---

示例4：

//计算strchr的时间复杂度？const char* strchr(const char* str, int character)
{const char* p_begin = str;while (*p_begin != character){if (*p_begin == '\0')return NULL;p_begin++;}return p_begin;
}

画图表示：

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

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

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

因此示例4的时间复杂度应该为：O(N)

---

示例5：冒泡排序

//计算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;}
}

画图表示：

---

示例6：对数的计算

//求时间复杂度void func5(int n)
{int cnt = 1;while (cnt < n){cnt *= 2;}
}

画图表示：

注：log 的底数可写可不写，如果底数为10可写成 lg

---

示例7：递归的计算

//计算阶乘递归Fac的时间复杂度？long long Fac(size_t N)
{if (0 == N)return 1;return Fac(N - 1) * N;
}

画图表示：

---

四、空间复杂度

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

空间复杂度计算规则基本跟时间复杂度类似，也使用大O渐进表示法。

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

空间复杂度计算示例

示例1：冒泡排序

//计算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;}
}

画图表示：

示例2：递归函数

//计算阶乘递归Fac的空间复杂度？long long Fac(size_t N)
{if (N == 0)return 1;return Fac(N - 1) * N;
}

画图表示：

---

五、常见复杂度对比

常见的复杂度有：n、logn、n*logn、n的平方、n的三次方、2的n次方、n的阶乘

解析：很明显，n的平方、n的三次方、2的n次方、n的阶乘这些复杂度都比较高。而n、logn、n*logn这些复杂度就比较低，算法的效率比较高。

---

总结

        以上就是本文的全部内容，感谢支持