algorithm - 在 O(nlog*n) 和 O(n) 之间？

Question

O(n logstar(n) ) 和 O(n) 之间是否存在真正的复杂性？我知道 O(n sqrt(logstar(n))) 和其他类似函数介于这两者之间，但我的意思是不是由 logstar(n) 组成的原始函数。

Answer 1

是的，有。最著名的例子是 Ackermann inverse function α(n)，其增长速度比 log* n 慢得多。它出现在像不相交集森林数据结构这样的上下文中，其中每个操作的摊销成本为 O(α(n))。

您可以将 log* n 视为您需要将 log 应用于 n 以将值降至某个固定常数(例如，2)的次数。然后您可以将其概括为 log** n，这是您需要将 log* 应用于 n 以将值降至 2 的次数。然后您可以定义 log*** n、log**** n , log***** n 等类似的方式。 α(n) 的值通常作为您需要放入 log^**...* n 中的星数给出，以使该值降至 2，因此它的增长速度比迭代对数函数。

直观上，你可以把log n看成求幂的倒数(重复乘法)，log* n看成tetration的倒数。 (重复取幂)，log** n 作为 pentation 的倒数(重复四次运算)等。阿克曼函数有效地将求幂的 n 阶泛化应用于数字 n，因此它的倒数对应于您需要应用多高的求幂级别才能达到它。这导致了一个令人难以置信的缓慢增长的函数。

我见过在严肃的环境中使用的最滑稽的缓慢增长函数是 α*(n)，您需要将阿克曼反函数应用于数字 n 以将其降至某个固定值的次数持续的。几乎无法想象您必须向此函数输入多大的输入才能返回接近于 10 的任何值。如果您好奇，the paper that introduced it is available here .