时间复杂度O(1) O(n) O(logn) O(nlogn)是什么意思?
程序员文章站
2022-07-12 22:48:55
...
在你渐渐迷失在你的人生道路上的时候,千万不要因为走的太久,而忘记了我们为什么出发,做码农,也要清楚自己如何才能用有效的土地种植出 出色的产品,于是细节就需要把握一下。
如果你有兴趣可以关注一下公众号 biglead 我的大前端生涯,获取每日学习资料
在描述算法复杂度时,经常用到O(1), O(n), O(logn), O(nlogn)来表示对应复杂度程度,可以用于表示时间复杂度,也用于表示空间复杂度。
类别 | 描述 |
---|---|
O(1) | 耗时与输入数据量大小无关 |
O(n) | 数据量增大几倍,耗时也增大几位 |
O(n^2) | 对 n 个数进行排序,需要扫描 n X n 次 |
O(logn) | 当数据量增大 n 倍时 ,扫描次数增大 logn 次(以2为底数) |
O(nlogn) |
时间复杂度的推导遵循3个原则:
- 如果运行时间跟n无关,是常数,则时间复杂度是O(1);
- 只保留时间函数中的最高阶项;
- 去掉高阶项前面的系数;
1 O(1)
若运行时间跟n的取值无关,即无论n取什么值,我的运行时间都不会变,则时间复杂度为O(1),只要基本操作执行次数是个常量,时间复杂度都为O(1)。
2 O(n)出现情况
O(n)一般出现在只有一个循环的情况下,执行次数是线性的,如下:
public void test(int number) {
for(int i = 0 ; i < number ; i++) {
... 其他代码
}
}
3 O(n^2)出现情况
O(n^2)一般出现在有嵌套循环的情况下
public void test(int n) {
int a = 1;
int b = 1;
for(int i = 0 ; i < n ; i++) {
for(int j = 0 ; j < n ; j++) {
a++;
}
b++;
}
}
上术循环中执行次数是 n x n 次 ,时间复制度为O(n^2)
推荐阅读
-
C语言:时间复杂度为O(1)的两则小程序
-
【JAVA】Leetcode1. 两数之和哈希表题解复杂度O(n)
-
实现一个栈,要求pop,push,Min,时间复杂度为O(1)
-
算法————双栈实现队列、双队列实现栈、实现一个栈Push(出栈)Pop(入栈)Min(返回最小值的操作)的时间复杂度为O(1)
-
ST算法_求RMQ问题_时间复杂度O(n*log2(n))+O(1)
-
时空复杂度(时间复杂度/空间复杂度)O(1)、O(n)、O(n^2)、O(log n)、O(n log n)是什么意思
-
时间复杂度O(1) O(n) O(logn) O(nlogn)是什么意思?
-
Java算法(递归):两个不同长度的有序数组求第k小的元素(时间复杂度为:O(log(m1 + m2)))。
-
浅谈Java如何实现一个基于LRU时间复杂度为O(1)的缓存
-
【数据结构】LRU,从O(n)复杂度到O(1)