lg*(n) 时间复杂度是否优于 lg(n)？
Is lg*(n) time complexity better than lg(n)?
我想了解 lg*(n) [log*(n) base 2] 与 lg(n) 相比的时间复杂度，我想知道它们中哪个更快...有人可以解释一下吗是吗？提前致谢。
我以前从未见过 lg*(n) 表示法，但我假设您指的是对数基数 2 与对数基数 10。事实证明 log2(N) == log10(N) * 3.32192809489...，这是一个常数因子差异，并且我们在分析算法复杂性时放弃了常数因子。结果，所有的对数都被认为是相等的，我们不需要费心在算法复杂度中指定底数。
在研究实际运行时时，log10(N) 比 log2(N) 快，但开发人员很少真正以这种方式分析运行时，他们通常使用分析器来进行。
根据维基百科，迭代对数 (log*) 是增长最慢的时间复杂度之一。事实上，在所有常用的复杂度中，它是第二慢的，仅次于反阿克曼函数。这意味着它比日志函数增长得慢得多，因此完成得快得多。
来源：https://en.wikipedia.org/wiki/Iterated_logarithm#Analysis_of_algorithms
我想了解 lg*(n) [log*(n) base 2] 与 lg(n) 相比的时间复杂度，我想知道它们中哪个更快...有人可以解释一下吗是吗？提前致谢。
我以前从未见过 lg*(n) 表示法，但我假设您指的是对数基数 2 与对数基数 10。事实证明 log2(N) == log10(N) * 3.32192809489...，这是一个常数因子差异，并且我们在分析算法复杂性时放弃了常数因子。结果，所有的对数都被认为是相等的，我们不需要费心在算法复杂度中指定底数。
在研究实际运行时时，log10(N) 比 log2(N) 快，但开发人员很少真正以这种方式分析运行时，他们通常使用分析器来进行。
根据维基百科，迭代对数 (log*) 是增长最慢的时间复杂度之一。事实上，在所有常用的复杂度中，它是第二慢的，仅次于反阿克曼函数。这意味着它比日志函数增长得慢得多，因此完成得快得多。
来源：https://en.wikipedia.org/wiki/Iterated_logarithm#Analysis_of_algorithms