小哦和小omega时间复杂度

Question

据我所知，小-哦应该有一个n的极限，接近于=0的(函数/小-哦，ω函数)的无穷大，对于小ω，这个极限应该等于无穷大。然而，有没有可能会有多个小哦和小omegas来实现这个限制呢？

也就是说，有没有可能有许多小欧姆和小欧米加可以满足一个方程？

Answer 1

是。Little-o是一种上界，little-omega是一种下界。一般而言，已知上界的任何上界本身都是上界。同样地，任何已知下界的下界本身也是一个下界。所以总是有无限多的上界，通常也有无限多的下界。

在下界中“通常”的原因是，0在非负函数中没有下界，而且通常在时间复杂性方面，你永远找不到任何常量的小ω。但是如果f(n)是无穷大的，那么你就会得到log(f(n))，log(log(f(n))，log(log(log(f(n)))，...下界的无穷序列。

至于上界，它是“总是”的，因为你可以将任何正函数乘以n，n^2，n^3，...以获得无限数量的严格更大的上界。