算法复杂度 n*(m+n)^2

Question

我写了一段代码如下:

for( i = 0 ; i < n; i++){
    for( j = 0; j < m + i; j++){
        for( k = 0; k < m + i; k++){
            dosomething();
         }
     }
}    

所以平均时间复杂度是 O(n*(m+n/2)*(m+n/2))？那么最坏的情况是什么？我很困惑。

Answer 1

您的算法在最坏情况、最佳情况和平均情况下的复杂度都相同。

对于大小为 (n,m) 的每个输入，它始终执行相同数量的指令。

• 最坏的情况是您将对某些输入 n,m 执行的最大可能步数。这是 O(n*(n+m)^2)，并且可以通过显示中间和内部循环比从 n+m/2< 花费更多时间来轻松证明 直到 n+m，并且因为它在 O(n*(n+m)^2) 中，所以也是算法。
• 同样 - 对于最好的情况，对于给定的 n,m 必须采取相同数量的步骤。
• 平均情况是将在大小为 n,m 的输入上完成的预期操作数 - 但确切的输入在这里并不重要，只有大小为 n 和 m - 所以这将保持不变