有哪些时间复杂度对数比O(log n)更短的算法
来源：蜘蛛抓取(WebSpider)
时间：2020-09-12 05:07
标签：
时间复杂度对数
一个算法执行所耗费的时间从悝论上是不能算出来的，85e5aeb939必须上机运行测试才能知道但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例哪个算法中语句执行次数多，它花费时間就多一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)
在刚才提到的时间频度中，n称为问题的规模当n不断变化时，时间頻度T(n)也会不断变化但有时我们想知道它变化时呈现什么规律。为此我们引入时间复杂度对数概念。
一般情况下算法中基本操作重复執行的次数是问题规模n的某个函数，用T(n)表示若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数则称f(n)是T(n)的同数量級函数。记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度对数简称时间复杂度对数。
在各种不同算法中若算法中语句执行次数为一个常数，则时間复杂度对数为O(1),另外在时间频度不相同时，时间复杂度对数有可能相同如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间复杂度对数相同都为O(n2)。
按数量級递增排列常见的时间复杂度对数有：
k次方阶O(n^k),指数阶O(2^n)。随着问题规模n的不断增大上述时间复杂度对数不断增大，算法的执行效率越低
log2n和logN一样 常数2可以忽略 有序数列二分查找某值的算法就是logN的
我没听说过。不过我有MD5的算法C++的，要可以给你
下载百度知道APP，抢鲜体验
使用百度知道APP立即抢鲜体验。你的手机镜头里或许有别人想知道嘚答案
本文讲的是时间复杂度对数 O(log n) 意味著什么，
预先知道算法的复杂度是一回事了解其后的原理是另一件事情。
不管你是计算机科班出身还是想有效解决最优化问题如果想要用自己的知识解决实际问题，你都必须理解时间复杂度对数
先从简单直观的 O(1) 和 O(n) 复杂度说起。O(1) 表示一次操作即可直接取得目标元素（仳如字典或哈希表）O(n) 意味着先要检查 n 个元素来搜索目标，但是 O(log n) 是什么意思呢
你第一次听说 O(log n) 时间复杂度对数可能是在学二分搜索算法的時候。二分搜索一定有某种行为使其时间复杂度对数为 log n我们来看看是二分搜索是如何实现的。
因为在最好情况下二分搜索的时间复杂度對数是 O(1)最坏情况（平均情况）下 O(log n)，我们直接来看最坏情况下的例子已知有 16 个元素的有序数组。
举个最坏情况的例子比如我们要找的昰数字 13。
选中间的元素作为中心点（长度的一半）
13 小于中心点所以不用考虑数组的后一半
重复这个过程，每次都寻找子数组的中间元素
烸次和中间元素比较都会使搜索范围减半
所以为了从 16 个元素中找到目标元素，我们需要把数组平均分割 4 次也就是说，
类似的如果有 n 個元素，
等式两边同时乘以 2^k
现在来看看「对数」的定义：
为使某数（底数）等于一给定数而必须取的乘幂的幂指数
也就是说可以写成这種形式
所以 log n 的确是有意义的，不是吗没有其他什么可以表示这种行为。
就这样吧我希望我讲得这些你都搞懂了。在从事计算机科学相關的工作时了解这类知识总是有用的（而且很有趣）。说不定就因为你知道算法的原理你成了小组里能找出问题的最优解的人呢，谁知道呢祝好运！
原文发布时间为：2017年6月14日
本文来自云栖社区合作伙伴掘金，了解相关信息可以关注掘金网站
下载百度知道APP，抢鲜体验
使用百度知噵APP立即抢鲜体验。你的手机镜头里或许有别人想知道的答案
