sup*_*ha1 -3 algorithm big-o time-complexity asymptotic-complexity
我们已经知道一些算法的渐近时间复杂度是n的函数,如
O(log*n),O(log n),O(log log n),O(n ^ c),0 <c <1,....
我可以知道作为n的函数的最小算法的渐近时间复杂度是多少？
更新2:O(1)是我们可以进行的最小时间复杂度,但是n的下一个最小的众所周知的函数是什么？据我研究:
O(alpha(n)):逆Ackermann:使用不相交集的每次操作的摊销时间
或O(log*n)迭代对数Hopcroft和Ullman在不相交集上的查找算法
除了琐碎之外O(1),答案是:没有一个.
如果某些东西不存在O(1)(也就是说n -> infinity,计算时间变为无穷大),无论n你找到什么边界函数,总会有一个较小的:只需要取一个边界函数的对数.你可以无限地做到这一点,因此没有最小的非常数边界函数.
但是在实践中,当你达到逆Ackermann函数时,你应该不用担心:)