algorithm - 该算法的时间复杂度是否正确？

Question

我已经解决了波纹管算法，发现时间复杂度为

O(nlgn*log(base3)n)

for (a=1;a<=n;a++)

   for (b=1;b<=n/2;b++)

     for (c=1;c<=n;c*=3)

        print("A")

现在我有了另一个算法:

for (a=1;a<=n;a++) 

      for (b=1;b<=a^2;b++)

          for (c=1;c<=n/2;c++)

            print("A2")

时间复杂度会不会是O(n^4 lgn)？如果不是请解释原因。谢谢

Answer 1

恐怕你说第一个算法的时间复杂度是 O(n * lgn * log₃n) 是错误的。它是 O(n² * log₃n)。 b 的循环在 O(n) 中运行而不是在 O(lgn) 中运行。

在第二个算法中，让我们看一下 c循环，它是 T_c = O(n)。如果我们省略 c循环我们实际上会在 O(n) 中减少时间所以 c循环带来了 n 的乘数到时间复杂度公式。

我们来看看a和 b . b取决于 a 的值.正文次数b将执行的循环是

T_a,b = 1 + 4 + 9 + 16 + ... + n²

这是众所周知的自然数平方和公式。

∑n² = n(n+1)(2n+1)/6 = O(n³)

最终我们有

T_a,b,c = T_a,b * T_c = O(n³ ) * O(n) = O(n⁴)

我看到你因为某种原因联系 n/2与 O(lgn)。循环 for(i=1;i<=n/2;i++)运行次数比 for(i=1;i<=n;i++) 少两倍，不是吗？它们都有复杂度 O(n)。与lgn无关。