time-complexity - 时间复杂度的乘法？

Question

我知道，当您将两个时间复杂度相乘时，您只需像往常一样将它们相乘，例如时间复杂度n log n乘以时间复杂度n将为您的时间复杂度为(n^2) log n.

但是界限在哪里发挥作用呢？那么如果n log n是上界和n也是上界，它们的乘积会是怎样的界呢？对于下限上限和紧密绑定的其他组合，它会是什么？（例如，上界 x 紧密绑定、上界 x 下界和紧密绑定 x 下界。）

谢谢你的帮助。

Answer 1

这是一道纯数学题：

f(x)是O(g(x))当且仅当存在M，x0这样|f(x)| <= M*|g(x)|对于所有x > x0。您将在大多数基本复杂性书籍中看到这一点。

所以假设f(x)isO(F(x))和g(x)is O(G(x))。然后|f(x)| <= M_f * |F(x)|为所有人x > x0F和|g(x)| <= M_g * |G(x)|所有人x > x0G。

|f(x) * g(x)| = |f(x)| * |g(x)| <= M_f * M_g * |F(x)| * |G(x)|尽管如此x > max(x0F, x0G)，复杂性确实成倍增加（写f(x) * g(x)并应用于big-O的定义）O(F(x) * G(x))M = M_f * M_gx0 = max(x0f, x0g)

Answer 2

因此，如果 n log n 是上限，并且 n 也是上限，那么它们的乘积将是什么类型的界限？

一个上限。请参阅任何好的教科书答案以进行形式分析；将这两个上限相乘的直观含义是“如果您最多只能执行n lg n次操作，每个操作最多n次，那么您最多执行n ² lg n工作”。

上界 × 紧界

紧界既是上限又是下界，所以这是一个上限。

紧密绑定×下限

……同样的道理，这是一个下限。

上限 × 下限

没有一般规律。假设您至少执行了 n ² 次操作，最多n次。这可能根本没有工作，或者指数数量，或者任何更大的东西。