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看作您需要将日志应用到n以将该值降低到某个固定常量（例如2）的次数。然后，您可以将其推广到log ** n，这是您需要将log *应用于n以将值降至2的次数。然后可以定义log *** n，log **** n ，log ***** n等以类似的方式。通常将α（n）的值作为您需要将日志数^{** ... *} n中的值减至2，因此其增长速度比迭代对数函数慢得多。

直观地说，你可以把日志的n为幂（重复乘法）的倒数，数* N为tetration（重复幂）的倒数，数** n的pentation（重复迭代幂次）的倒数，等等.Ackermann函数将n次幂的n阶泛化有效地应用于数n，所以它的逆矩阵对应于需要应用的指数级别有多高。这导致了令人难以置信的缓慢增长的功能。

我曾经见过的最滑稽的慢速增长函数在一个严肃的语境中使用是α *（n），您需要将阿克曼反函数应用到数字n以将其降到某些值固定不变。这是几乎不可思议的多大的输入，你必须把这个函数返回接近，例如10。如果你很好奇，the paper that introduced it is available here。