- 站点信息
- 问题反馈
- 邮箱：[email protected]
- 吐槽一下
关注微信
©2020-2025 ioDraw All rights reserved,
Privacy Policy
开始之前有两个知识点要明确一下：
1、时间复杂度可以根据程序运行的次数来判断
2、时间复杂度的系数可以忽略
比如下面这个例子：
第一种情况程序只运行了一次，第二种情况程序运行了三次所以应该是O(3*1)=O（3），而系数可以忽略，所以最终结果就是O(1).
下面是常用的几种时间复杂度
接着我们还是举例子来看，下面的第一个程序循环了n次，所以它的时间复杂度是O（N），如果n等于5那么，就执行了5次，那么时间复杂度就是O(5)，也就是常数复杂度O(1)。
第二个我们发现它是一个循环中又嵌套了一个循环，而且两次循环的次数都是n所以它的时间复杂度就是n的平方，因为i=1时要输出n次，等于2的时候也要输出n次…所以是n个n相加那就是n
乘n也就是n的平方，如果再嵌套一个n次的循环它就是n的三次方。
在这儿我们做一下小拓展，就是如果我们把第二个程序的两个循环改成并列关系，那么它的时间复杂度又是多少呢？
毫无疑问它执行了n次，又执行了n次，那就是2n次，根据上面的规则时间复杂度就是O(N)。
简而言之，也就是如果是嵌套执行，嵌套几次时间复杂度就是O(n的多少次方)
不管并列多少次，它的时间复杂度都是O(N)
我们还是接着看例子，如果我们把第一个程序的n改为4，那么这个函数体执行几次呢？大家不妨找张纸算一算，其实挺简单的，你只要明白4<4是不成立的就行，哈哈哈哈哈，所以他是执行了2次，所以他的执行次数就是log（n），那么时间复杂度就是O（log（n））这儿是以2为底的。
第二个是斐波那契数列代表的递归的时间复杂度，我们在后面讲
时间复杂度曲线
我们可以看到当n小于5的时候时间复杂度其实都是差不多的，但是随着n越来越大，你会发现指数级的它涨的是非常快的，也就是大家在写程序的时候如果可以将一个时间复杂度为2的n次方，降到n的平方，那么你的收益是非常高的。
所以我们需要反复强调一个点，就是大家在写程序的时候一定要对自己程序的时间复杂度和空间复杂度有所了解，而且是养成习惯，写完了以后能够下意识的分析出这段程序的时间和空间复杂度，还有就是能够用最简洁的时间，空间复杂度完成这段程序的话，基本上是一个顶尖职业选手的必备素养。
下面我们来看递归函数的时间复杂度
为了更好的表示我们进行递归的过程，我们需要画一个叫做递归树的东西来辅助我们理解整个程序
下面我们来看一个例子
这是一个求斐波那契数列的第n项的函数，我们来看它的时间复杂度，假如n等于6，那么直接跳到
fib（5）+fib（4）
而分别求5和4的时候又要分成两步，我们看上面这个树状图，每一次每个结点都要分成两步，也就是第一层只有1个，第二层变成两个，第三层变成四个，第四层变成八个，也就是指数函数被。
主定理
主定理是用来计算递归函数的时间复杂度的，下面给出了四种常用算法的时间复杂度
分别是
1、二分查找，一般发生在一个有序数列中找到你要的目标数，所以它每次都一分为二，只查一边
2、二叉树的遍历，相当于把每个元素访问了有且仅有一遍
3、有序二维矩阵的二分查找
4、归并排序
上面四种情况，除了二分查找的时间复杂度是logn以外，其他三种的时间复杂度均为O(N)，因为要访问有且仅有一次其中的结点，其中的N为结点数。
以上图片来自极客时间