for（）循環在if（）語句內時如何影響運行時？

Question

說我們有這樣的代碼：

doSomething(int n) { 
    for(int i = 0; i < n; i++) { 
     if (i % 7 == 0) { 
      for(int j = 0; j < n; j++) { 
       print("*"); 
      } 
     } 
    } 
} 

是什麼（用樣張/工作）的大O和大歐米伽運行時間？ 我的思想正在被if（）語句和如何證明big-omega所吹捧（因爲對於big-o我們可以忽略這個條件，因爲它是一個上限）。 任何幫助，非常感謝。謝謝！

Answer 1

我們首先嚐試以更清楚地暴露運行時的方式重寫事物。例如，內環有Θ（N）運行時，讓我們改寫這樣的代碼：

for(int i = 0; i < n; i++) { 
    if (i % 7 == 0) { 
     do Θ(n) work 
    } 
} 

現在，想想當這個循環運行時會發生什麼。每7次迭代中就有一次會觸發內部循環，並執行Θ（n）工作，剩餘的六分之七不會執行每次迭代的Θ（1）工作。這意味着，所做的總功是

N（（1/7）× Θ（N）+（6/7）× Θ（1））

= N（Θ（N）+ Θ（1））

= N（Θ（n））的

= Θ（N ）。

換句話說，這裏所做的總功是Θ（N ）。而且這也是有道理的，因爲基本上，如果陳述只是將所做的工作減少了1/7倍，而大O標記忽略了不變的因素。

---

您最初寫的問題，此代碼：

for(int i = 0; i < n; i++) { 
    if (n % 7 == 0) { 
     for(int j = 0; j < n; j++) { 
      print("*"); 
     } 
    } 
} 

這裏是我原來的答覆：

首先，讓我們試圖重寫更清楚地暴露了運行時的方式事情。例如，內環有Θ（N）運行時，讓我們改寫這樣的代碼：

for(int i = 0; i < n; i++) { 
    if (n % 7 == 0) { 
     do Θ(n) work 
    } 
} 

所以，現在讓我們想想這裏發生了什麼。有可能發生的事情有兩種可能性。首先，n可能是7的倍數。在這種情況下，if語句每次觸發，並且在n個外循環迭代中的每一個上，我們都會執行Θ（n）。因此，我們可以說在最壞的情況下完成的總工作將是Θ（n ）。我們不能收緊這個界限，因爲隨着n變得越來越大，我們繼續跑到越來越多的七倍。其次，n可能不是7的倍數。當發生這種情況時，我們做了Θ（n）循環迭代，它們都做了Θ（1），因此在最好的情況下，我們會做Θ（n）全部工作。

總體而言，這意味着，在最壞的情況下，我們做Θ（N ）工作，並在最好的情況下，我們做Θ（n）的工作。因此，我們可以說該函數的運行時間是O（n ）和Ω（n），但我認爲對最佳和最壞情況運行時的更精確的描述會提供更多的信息。

這裏分析的關鍵是意識到，如果陳述要麼總是要開火或者永遠不會開火。這使我們更容易將推理分爲兩個獨立的案例。

請記住，大O分析不僅僅是將一堆事物放在一起。這是關於如果我們要運行它，然後考慮邏輯將如何發揮，那麼程序實際上會做什麼。如果你嘗試用這種方式來處理大O分析，你很少會浪費你的時間。