最小算法的，因爲我們已經知道了一些算法的時間複雜度正

Question

的函數時間複雜度爲n如

O（日誌* N），O（日誌N），O的功能（日誌log n）的，爲O（n^c）與0 <ç< 1，...

我能知道什麼是最小算法的爲n的函數時間複雜？

• 更新1：我們尋找n的漸近時間複雜度函數。 O（1）是最小的，但它沒有n。

• 更新2：O（1）是我們可以去的最小時間複雜度，但是下一個最小的知名函數是什麼？據我研究：

  O（α（n））的：逆阿克曼：使用不相交的每個操作的分期時間設定

  或O（日誌* N）迭代對數Hopcroft和烏爾曼的查找算法上一個脫節組

Answer 1

除了微不足道的O(1)，答案是：沒有一個。

如果事情不是O(1)（即與n -> infinity，計算時間趨近於無窮），你會發現什麼的n包圍功能，總有一個較小的一個：只取限界函數的對數。你可以無限地做到這一點，因此沒有最小的非常量邊界函數。

然而，在實踐中，你可能應該停止擔心，當你到達inverse Ackermann function :)

Answer 2

1. 這是沒有必要的，一個給定的算法的複雜性通過衆所周知的功能是表達。另請注意，大哦不是給定算法的複雜性。這是複雜性的上限。
2. 您可以根據需要構建函數增長緩慢，例如對於任意k，都可以使用函數n ^1/k。
3. O(1)就複雜性而言可以達到的最低限度，嚴格來說1是一個有效的函數，它只是常數。

編輯：我能想到的一個非常緩慢的增長功能是iterated logarithm爲disjoint set forest既路徑壓縮和聯盟的等級來實現的複雜性。

Answer 3

無論有什麼建議，總會有一個「較小的算法」。

O(log log log log(n)) < O(log log log(n)) < O(log log (n)) < O(log(n)). 

你可以儘可能多的log你想要的。但我不知道是否有這些真實生活的例子。

所以我的答案是你會越來越接近O(1)。