时间复杂度请原谅我也是一个标题党! 关于时间复杂度和空间复杂度分析的文章其实不少,但大多数都充斥着复杂的数学计算,让很多读者感到困惑,我就不跟大家扯皮了,关于什么是渐近分析、最坏时间复杂度、平均时间复杂度和最好的时间复杂度,以及大 记法等等,大家好好花点儿时间看看严老师的书就会了。 我们从代码和实现的层面讲讲,如何计算你写的代码的时间复杂度? 任何一门语言的逻辑结构无非三种:顺序结构、循环结构和分支结构,但是真正影响到时间复杂度只有循环结构,如果分支结构影响复杂度,也是因为分支内部包含了循环。 循环的实现有 如果一个函数(语句)不包含循环、迭代或非常数时间的函数,则可以认为函数为 的时间。 // 非循环或者递归语句或函数 比如交换两个数的
一个循环如果仅仅运行常数次,那么时间复杂度也可以当作 来处理: // c 表示一个常量 如果循环控制变量
,嵌套循环的时间复杂度等于最内层语句的执行次数。例如,下面示例循环的时间复杂度为 : for (int i = 1; i <= n; i += c) { 如果循环控制变量
简单地分析一下,循环控制变量到达 的顺序为 ,如果我们令 ,那么 ,也就是循环到达 n 仅仅会执行 次,复杂度自然为 量级。 比如二分查找(binary search)的迭代实现的时间复杂度就是 : int binarySearch(int arr[], int l, int r, int x) 如果循环控制变量 情况一:
这种情况下, 情况二: // fun(i) 表示为 i 开方或者开立方
如果程序中包含多个循环,又该如何时间复杂性?如果程序中存在多个连续循环时,时间复杂度为多个单循环的时间复杂度之和。
上面程序的时间复杂度为 ,当 时,则 ,依旧是 量级。 如果循环内部包含大量的 |
题型 | 时间复杂度 |
---|---|
数组、动态规划 | for 循环执行次数 |
链表 | while 循环执行次数 |
栈、队列 | 栈或者队列的大小 |
二叉树 | 结点个数 |
回溯法、BFS/DFS | 元素个数 O(n) |
二分查找 | log(n) |
分治法 | log n (归并排序、快速排序) |
当然这也只是一个比较粗略的概括,时间复杂度的分析无定法,仅仅是大家的一个共识而已,最好的方法是,将你的代码结合数据跑起来,计算它的运行时间,但是这也需要大家规定设备的型号和运行内存等等硬件。
谁说深究不是一种品质呢?如果你真的对时间复杂度和空间复杂度感兴趣,那就研究下去!!!
|