lg*(n)的时间复杂度比lg(n)好吗？
lg*(n)的时间复杂度比lg(n)好吗？
提问于 2020-04-03 02:22:45
我正在尝试理解lg*(n) log*(n)基数2与lg(n)相比的时间复杂度，我想知道他们中的哪一个是faster...can，有人能解释一下吗？提前谢谢。
回答 2
Stack Overflow用户
回答已采纳
发布于 2020-04-03 03:29:57
根据维基百科的说法，迭代对数(log*)是增长最慢的时间复杂度之一。事实上，在所有常用的复杂度中，它是第二慢的，仅次于逆Ackerman函数。这意味着它的增长速度比log函数慢得多，因此完成的速度也要快得多。
来源：https://en.wikipedia.org/wiki/Iterated_logarithm#Analysis_of_algorithms
Stack Overflow用户
发布于 2020-04-03 02:31:57
我以前从未见过lg*(n)表示法，但我假设你指的是对数底2和对数底10。事实证明，log2(N) == log10(N) * 3.32192809489...是一个常数因子差，在分析算法复杂性时，我们去掉了常数因子。因此，所有的对数都被认为是相等的，我们不需要费心在算法复杂度上指定基数。
在研究实际的运行时，log10(N)比log2(N)更快，但很少有开发人员真正以这种方式分析运行时，他们通常使用分析器进行分析。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/60998443
复制相关文章
相似问题
腾讯云开发者
