小编sup*_*ha1的帖子

我们已经知道一些算法的渐近时间复杂度是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)):逆Ackermann:使用不相交集的每次操作的摊销时间

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