<pre style="color: rgb(0, 0, 0);font-size: 16px;letter-spacing: 0.544px;text-align: center;widows: 1;word-spacing: 1px;background-color: rgb(255, 255, 255);">
设为“星标”，重磅干货，第一时间送达
时间复杂度
请原谅我也是一个标题党！
关于时间复杂度和空间复杂度分析的文章其实不少，但大多数都充斥着复杂的数学计算，让很多读者感到困惑，我就不跟大家扯皮了，关于什么是渐近分析、最坏时间复杂度、平均时间复杂度和最好的时间复杂度，以及大 记法等等，大家好好花点儿时间看看严老师的书就会了。
我们从代码和实现的层面讲讲，如何计算你写的代码的时间复杂度？
任何一门语言的逻辑结构无非三种：顺序结构、循环结构和分支结构，但是真正影响到时间复杂度只有循环结构，如果分支结构影响复杂度，也是因为分支内部包含了循环。
循环的实现有 for 和 while 两种形式，但是本质都是一样的，我们接下来均以 for 循环进行说明。
如果一个函数（语句）不包含循环、迭代或非常数时间的函数，则可以认为函数为 的时间。
<code style="overflow-x: auto;padding: 16px;color: #333;background: #f8f8f8;display: -webkit-box;font-family: Operator Mono, Consolas, Monaco, Menlo, monospace;border-radius: 0px;font-size: 12px;-webkit-overflow-scrolling: touch;">// 非循环或者递归语句或函数
int love = 520;
比如交换两个数的 swap() 函数的时间复杂度就是 :
void swap(int *xp, int *yp)
{
int temp = *xp;
*xp = *yp;
*yp = temp;
}
一个循环如果仅仅运行常数次，那么时间复杂度也可以当作 来处理：
// c 表示一个常量
for(int i = 0; i < c; i++) {
// O(1) 表达式
}
如果循环控制变量 i 递增/递减的步长为一个常数 ，则认为循环的时间复杂度为 。例如，以下函数的时间复杂度为 ：
// c 是一个正整数常量
for(int i = 0; i < n; i += c) {
// O(1) 表达式
}
-------------------------------
for(int i = n; i > 0; i -= c) {
// O(1) 表达式
}
，嵌套循环的时间复杂度等于最内层语句的执行次数。例如，下面示例循环的时间复杂度为 ：
for (int i = 1; i <= n; i += c) {
for (int j = 1; j <= n; j += c) {
// O(1) 表达式
}
}
for (int i = n; i > 0; i -= c) {
for (int j = i+1; j <= n; j += c) {
// O(1) 表达式
}
}
如果循环控制变量 i 乘以或除以一个常数 ，则循环的时间复杂度为 量级：
// c 是一个正整数常量
for(int i = 1; i < n; i *= c) {
// O(1) 表达式
}
-------------------------------
for(int i = n; i > 0; i /= c) {
// O(1) 表达式
}
简单地分析一下，循环控制变量到达 的顺序为 ，如果我们令 ，那么 ，也就是循环到达 n 仅仅会执行 次，复杂度自然为 量级。
比如二分查找（ ）的迭代实现的时间复杂度就是 ：
int binarySearch(int arr[], int l, int r, int x)
{
while (l <= r) {
int m = l + (r - l) / 2;
if (arr[m] == x)
return m;
if (arr[m] < x)
l = m + 1;
else
r = m - 1;
}
return -1;
}
如果循环控制变量 i 以指数级别增加或者减少，则时间复杂度为 量级。
情况一：
for(int i = 2; i <= n; i = pow(i, k)) {
// O(1) 表达式或语句
}
这种情况下，i 的取值为 ，而最后一项一定小于等于 ，即 ，也就是说循环执行了 次，每一次迭代的时间为常数时间，则上面的迭代总的时间复杂度为 量级。
情况二：
// fun(i) 表示为 i 开方或者开立方
for(int i = n; i > 0; i = fun(i)){
// O(1) 表达式或语句
}
i 的取值为， ，所以迭代总共执行 次，时间复杂度为 量级。
如果程序中包含多个循环，又该如何时间复杂性？
如果程序中存在多个连续循环时，时间复杂度为多个单循环的时间复杂度之和。
for (int i = 1; i <= m; i += c) {
// O(1) 表达式或语句
}
for (int i = 1; i <= n; i += c) {
// O(1) 表达式或语句
}
上面程序的时间复杂度为 ，当 时，则 ，依旧是 量级。
如果循环内部包含大量的 if...else... 语句时，又该如何计算时间复杂度？
在最好、平均和最差时间复杂度中递归算法时间复杂度，我们一般只关注最坏时间复杂度。考虑最坏的情况，当if...else... 条件中的语句导致执行时间复杂度的增加，就需要将其计算到最坏时间复杂度中。
int search(int arr[], int n, int x)
{
int i;
for (i = 0; i < n; i++) {
if (arr[i] == x)
return i;
}
return -1;
}
例如，考虑上面的线性搜索函数，其中我们考虑元素出现在数组 arr[] 的末尾或根本不存在的情况，分别对应 和 的时间复杂度，但是我们仅关注最坏的时间复杂度 。
当代码太复杂而无法考虑所有 if...else 情况时，我们可以忽略 if...else 和其他复杂的控制语句来计算最坏情况下的时间复杂度。
递归算法的时间复杂度又该如何计算？
很多算法都是基于递归思想的，我们分析这些递归算法，可以得到关于时间复杂度的递归关系式。比如 的时间复杂度一般表示为 ，还有二分查找，汉诺塔问题等等，但是关于递归的时间复杂度并不简单。
对于递归的时间复杂度的计算主要有三种方式：
一、代入法：先对解进行猜想，然后用数学归纳法证明猜想的正确性。
已知 ，注意 前面的系数 ；
又很容易得到 和 之间的关系式，即 .
将 与 之间的关系式带入 当中，就是将所有的 替换为 ：
则， ，注意
就得到了 与 之间的关系式，
同理， 与 之间的关系为： ,
带入 ，得到 和 之间的关系式；
，注意
以此类推...
可以推知 与 之间的关系：
∴ 归并排序的时间复杂度为 量级。
二、主定理
令 和 1" data--type="-" style=""> 是常数， 是一个函数， 是定义在非负整数上的递归式：
其中我们将 解释为 或 ，那么 有如下渐近界：
若对某个常数 0" data--type="-" style=""> 有 ，则 .
若 ，则 .
若对某个常数 0" data--type="-" style=""> 有 ，且对某个常数 和所有足够大的 有 ，则 .
主定理对递归式 所提供的一种 “菜谱式” 的求解方法，关于主定理的证明就不在这里解释了，感兴趣可以看一下 《算法导论》4.6 节的主定理的证明。
我们这里直接 “下菜“ 即可。
已知 ；
首先和 对应起来
、 、
则
∴ .
即归并排序的时间复杂度为 .
三、递归树
在该方法中，我们绘制了一棵递归树，并计算了树的每一层所花费的时间。最后，我们总结了各级所做的工作。为了绘制递归树，我们从给定的递归开始，不断绘制，直到在级别之间找到一个模式。通常是算术或几何级数。
以递归关系 为例，其递归树可以表示为：
我们进一步打开表达式递归算法时间复杂度，以及表达式 :
继续把 ，拆分。
而为了计算 ，则需要一层一层地将树中的所有结点累加起来，即：
上面序列的几何级数的系数为 5/16，为了获得上限，我们可以无限趋近于无穷大，获得 ，时间复杂度为 量级。
是不是被这种方法搞得晕晕乎乎，没关系，这属于了解内容，当然想深究的可以看看算法导论。
你该不会到这里就结束了吧！
其实计算算法的时间复杂度还有一种方法，就是根据题型去判断计算：
题型时间复杂度
数组、动态规划
for 循环执行次数
链表
while 循环执行次数
栈、队列
栈或者队列的大小
二叉树
结点个数
回溯法、BFS/DFS
元素个数 O(n)
二分查找
log(n)
分治法
log n （归并排序、快速排序）
当然这也只是一个比较粗略的概括，时间复杂度的分析无定法，仅仅是大家的一个共识而已，最好的方法是，将你的代码结合数据跑起来，计算它的运行时间，但是这也需要大家规定设备的型号和运行内存等等硬件。
谁说深究不是一种品质呢？如果你真的对时间复杂度和空间复杂度感兴趣，那就研究下去！！！
推荐阅读：
太赞了！东北大学朱靖波，肖桐团队开源《机器翻译：统计建模与深度学习方法》
你们心心念念的MIT教授Gilbert Strang线性代数彩板笔记！强烈推荐！
GitHub超过9800star！学习Pytorch，有这一份资源就够了！强推！
你真的懂神经网络？强推一个揭秘神经网络的工具，ANN Visualizer
玩转Pytorch，搞懂这个教程就可以了，从GAN到词嵌入都有实例
是他，是他，就是他！宝藏博主让你秒懂Transformer、BERT、GPT！
fitlog！复旦邱锡鹏老师组内部调参工具！一个可以节省一篇论文的调参利器
Github开源！查阅arXiv论文新神器，一行代码比较版本差别，我爱了！
他来了！吴恩达带着2018机器学习入门高清视频，还有习题解答和课程拓展来了！
这块酷炫的Python神器！我真的爱了，帮助你深刻理解语言本质！实名推荐！
限时特惠:本站持续每日更新海量各大内部创业课程，一年会员仅需要98元，全站资源免费下载
点击查看详情
站长微信:Jiucxh声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。
