algorithm - Little-oh 和 Little-omega 时间复杂度

Question

据我所知，little-oh 应该有一个接近无穷大的 n 的极限(函数/little-oh,omega 函数)= 0，对于 little omega，极限应该等于无穷大。但是，是否有可能存在多个 little-oh's 和 little-omegas 使极限成立？

也就是说，是否有可能存在许多适合单个方程的小 oh 和小 omega？

Answer 1

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

下界中“通常”的原因是 0 在非负函数中没有下界，通常在时间复杂度上你永远不会找到 a 的 little-omega持续的。但是，如果 f(n) 趋于无穷大，那么您将得到 log(f(n))，log(log(f(n)), log(log(log(f(n))), ... 对于下界的无限系列。

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