算法Big Omega

Question

我在分析以下內容時遇到問題。

for b = 1 to n 
    for u = b to n 
     for i = b to u 
      Print 

我無法確定最壞情況的運行時間。 第一個循環運行n次，第二個循環運行（n（n + 1））/ 2次。 然後我相信第三個循環運行（n + 1）/ 2次。

但是我被告知它有一個運行時間O（n^3）。 因此，最好的情況下運行時間不能大於最壞的情況下的運行時間！ 如果可能的話，我希望能夠朝正確的方向努力！ 謝謝！

Answer 1

當它被激活時，第三個循環執行打印u-b + 1次{3}。當第二個循環被激活時，第三個循環對於從b到n的所有u被激活，即執行打印1 + 2 + 3 + ... n-b + 1次（替代u = 1,2，...， {3}中的3 ... n）。使用triangular numbers的公式，該計數等於（n-b + 1）（n-b + 2）/ 2 {2}。當第一個循環被激活時，第二個循環從1到n被激活，即執行Print n（n + 1）/ 2 +（n-1）n/2 +（n-2） （n-1）/ 2 + ... 1次（在{2}中代入b = 1,2,3，...;計數遞減）。

使用公式爲tetrahedral numbers，這等於n（n + 1）（n + 2）/ 6 {1}。

如果您在使用此方法時遇到問題，則可以手動模擬打印。

對於n = 1

* 

對於n = 2

* 
* * 

* 

對於n = 3

* 
* * 
* * * 

* 
* * 

* 

對於n = 4

* 
* * 
* * * 
* * * * 

* 
* * 
* * * 

* 
* * 

* 

...

您清楚地看到了尺寸減小的三角形圖案。三角形的面積隨着邊的平方增長。 總體積增長爲邊的立方體。