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。