在学术界,严格地讲,O(f(n))表示算法执行的上界。比如,归并排序算法的时间复杂度是O(nlogn)的,同时也是O(n^2)
在业界,我们就是用O来表示算法执行的最低上界。所以,我们一般不会说归并排序是O(n^2)的。
有一个字符串数组,将数组中的每一个字符串按照字母序排序;之后再将整个字符串数组按照字典序排序。整个操作的时间复杂度?
错误答案:O(n*nlogn + nlogn) = O(n^2logn)
正确解答:
假设最长的字符串长度为s;数组中有n个字符串 对着每个字符串排序:O(slogs) 将数组中的每一个字符串按照字母序排序:O(n*slog(s)) 将整个字符串数组按照字典序排序:O(s*nlog(n)) 所以:O(n*slog(s)) + O(s*nlog(n)) = O(n*s*logs + s*n*logn) = O(n*s*(logs+logn)) 整数比较是O(1),字符串的字典序比较是O(s), 所以整个字符串数组进行字典序排序是O(s*nlog(n))。
(1)O(n^2)的算法可以处理大约10^4级别的数据;
(2)O(n)的算法可以处理大约10^8级别的数据;
(3)O(nlogn)的算法可以处理大约10^7级别的数据;
递归调用有空间代价,一般递归深度有多少,占用的空间就有多少。
30n次基本操作:O(n)
二分查找法的时间复杂度是O(logn)的
不要看到for循环,就认为是一层O(n),下面是两个例子
例1:
不是O(n^2),而应该是O(nlog(n))。
例2:
是O(sqrt(n))。
再来看一下O(logn)的效率:
log2*N / logN = (log2 + logN) / logN = 1 + log2/logN
如果数据规模增加两倍,当数据量很大的时候,后面的一项可以忽略不计,也就是说运行时间几乎没有增长。
从而可以得知:
1.如果可以将顺序查找的问题转成二分查找的问题,那么就能大大提升效率。
2.O(n)和O(logn)有本质差别,同理,O(n^2)和O(nlogn)也有本质差别。
时间复杂度:O(logn)
如果递归函数中,只进行一次递归调用,递归深度为depth;在每个递归函数中,时间复杂度为T;则总体的时间复杂度为O(T*depth)。
例题:
根据前面O(logn)的性质,可知上面的幂运算比O(n)快很多。
上面函数和归并排序不同,归并排序每次递归数据量都有减少,也就是分治算法。
扫码关注腾讯云开发者
领取腾讯云代金券
Copyright © 2013 - 2025 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号:粤B2-20090059 深公网安备号 44030502008569
腾讯云计算(北京)有限责任公司 京ICP证150476号 | 京ICP备11018762号 | 京公网安备号11010802020287
Copyright © 2013 - 2025 Tencent Cloud.
All Rights Reserved. 腾讯云 版权所有