25

我在正在阅读的有关数据结构的书中遇到了这个术语O(log* N)。是什么log*意思？我在 Google 上找不到它，WolframAlpha也不明白。

4

4 回答 4

27

它被称为迭代对数函数。这是一个增长非常缓慢的功能。例如：

  • lg*(2) = 1
  • lg*(4) = 2
  • lg*(16) = 3
  • lg*(65536) = 4
  • lg*(2^65536) = 5/注意 (2^65536) 远大于可观测宇宙中的原子数/

或者在 Big O 的情况下，它几乎可以被视为常数时间。

于 2010-09-26T11:46:29.587 回答
23

它是迭代对数。有关许多不同时间复杂度的描述，请参见此处，有关迭代对数本身的更多详细信息，请参见此处。

迭代对数是在结果变为 1 或更少之前必须应用对数的次数。

于 2010-09-26T11:45:42.990 回答
5

log* (n) - “log Star n”，即“迭代对数”

简单来说，您可以假设 log* (n)= log(log(log(.....(log* (n))))

log* (n) 非常强大。

例子：

1) Log* (n)=5 其中 n= 宇宙中的原子数

2) 使用 3 种颜色的树着色可以在 log*(n) 中完成，而着色树 2 种颜色就足够了，但复杂度将是 O(n)。

3）在知道欧几里得最小生成树的情况下找到一组点的Delaunay三角剖分：随机O（n log * n）时间。

我希望你可以在 WolframAlpha 上像这样可视化Log* (n)检查这里

于 2014-09-30T06:25:55.857 回答
2

log* 是您需要应用对数函数的次数，直到您达到小于或等于 1 的值。例如：log*(16) = 3，因为 log 2 (log 2 (log 2 (16) )) = 1。

出于实际目的，您可以将其视为常数，因为此函数增长非常缓慢。

于 2017-08-12T14:14:59.347 回答