最小算法的渐近时间复杂度作为 n 的函数

Question

我们知道一些算法的渐近时间复杂度是n的函数比如

O(log* n), O(log n), O(log log n), O(n^c) 0< c < 1, ....

请问最小的算法的渐近时间复杂度是多少 n 的函数？

• 更新 1：我们寻找具有 n 的渐近时间复杂度函数。 O(1)是最小的，但它没有n。

• 更新 2：O(1) 是我们可以达到的最小时间复杂度，但是 n 的下一个最小的知名函数是什么？据我研究：

  O(alpha (n)) ：逆阿克曼：使用不相交集的每个操作的摊销时间

  或O(log * n)迭代对数Hopcroft和Ullman在不相交集上的查找算法

Answer 1

除了琐碎的O(1)，答案是：没有。

如果某物不是O(1)（即，n -> infinity，计算时间趋于无穷大），无论您找到n的任何边界函数，总会有一个更小的边界函数：只需取边界函数的对数。你可以无限地这样做，因此没有最小的非常数边界函数。

但是在实践中，当您达到 inverse Ackermann function :)

时，您可能应该停止担心

Answer 2

1. 给定算法的复杂性不必通过众所周知的函数来表达。另请注意，big-oh 不是给定算法的 复杂度。它是复杂度的上限。
2. 您可以构造随您想要的速度增长的函数，例如 n^1/k 对于任何 k。
3. O(1) 就复杂性而言是尽可能低的，严格来说 1 是一个有效函数，它只是常数。

编辑：我能想到的一个增长非常缓慢的函数是 iterated logarithm as complexity of disjoint set forest 通过路径压缩和按等级联合实现的。

Answer 3

总有一个 "smaller algorithm" 是什么建议。

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

你想放多少就放多少log。但我不知道这些是否有现实生活中的例子。

所以我的回答是你会越来越接近O(1)。