A. *_*ghi 3 algorithm complexity-theory big-o time-complexity asymptotic-complexity
O(n logstar(n))和O(n)之间是否存在真正的复杂性？我知道O(n sqrt(logstar(n)))和其他类似函数介于这两者之间,但我的意思是原始的,不是由logstar(n)组成的.
就在这里.最着名的例子是阿克曼逆函数 α(n),它比log*n生长得慢得多.它出现在像不相交森林数据结构这样的上下文中,其中每个操作的摊销成本为O(α(n)).
您可以将log*n视为需要将log应用于n以将值降低到某个固定常量(例如2)的次数.然后,您可以将此概括为log**n,这是您需要将log*应用于n以将值降低为2所需的次数.然后,您可以定义log***n,log****n ,以类似的方式记录*****等.α(n)的值通常以log **...* n中需要放置的星数给出,以使值降至2,因此它比迭代对数函数生长得慢得多.
直观地说,你可以把log n看作取幂的逆(重复乘法),log*n作为tetration的逆(重复取幂),log**n作为pentated的倒数(重复的tetration)等等.Ackermann函数有效地将求幂的n阶泛化应用于数n,因此它的倒数对应于你需要应用它的取幂程度有多高.这导致了令人难以置信的缓慢增长的功能.
我所见过的在一个严肃的语境中使用的最滑稽缓慢增长的函数是α*(n),你需要将Ackermann反函数应用于数n以将其降低到某个固定常数的次数.几乎不可想象的是你需要投入大量的输入才能找回任何接近10的东西.如果你很好奇,引入它的论文可以在这里找到.