什麼是有限循環程序的大哦效率？

Question

以下程序的效率如何，它是一個for循環，其運行時間爲有限數量。的時代。

for(int i = 0; i < 10; i++) 
{ 
    //do something here, no more loops though. 
} 

那麼，應該是什麼效率。 O（1）或O（n）？

Answer 1

這完全取決於for循環中的內容。此外，計算複雜度通常根據輸入的大小n測量，在您的示例中我看不到任何模型或代表或直接或間接編碼輸入大小的任何內容。只有恆定的10。

此外，雖然有時的計算複雜度的分析可能產生意外的，令人驚訝的結果，正確的說法是不「Big Oh」，而是Big-O。

Answer 2

當然O（1），因爲這裏沒有什麼不依賴於n的線性。

編輯： 讓循環體包含一些複雜的動作，其複雜度爲O（P（n））。如果我們有一個常數C的迭代次數，循環的複雜度爲O（C * P（n））= O（P（n））。

否則，現在讓迭代次數爲Q（n），取決於n。它使循環O（Q（n）* P（n））的複雜性成爲可能。

我只是想說，當迭代次數不變時，它不會改變整個循環的複雜性。

Answer 3

n in Big O notation表示輸入大小。我們不知道什麼是複雜性，因爲我們不知道for循環內發生了什麼。例如，也許有遞歸調用，取決於輸入大小？在這個例子中，整體是O(n)：

void f(int n) // input size = n 
{ 
    for (int i = 0; i < 10; i++) 
    { 
     //do something here, no more loops though. 
     g(n); // O(n) 
    } 
} 

void g(int n) 
{ 
    if (n > 0) 
    { 
     g(n - 1); 
    } 
} 

Answer 4

你只能說一些關於計算的某些特定輸入的複雜性。如果你循環10次是因爲你需要爲之工作的十個「東西」，那麼你的複雜性就是這些東西的O（N）。如果你只需要循環10次而不管有多少東西 - 並且處理時間在之內，循環不會隨着某些事物的數量而改變 - 那麼你的複雜度就是O（1）。如果沒有訂單大於1的「某些東西」，那麼將循環描述爲O（1）是公平的。

---

有點進一步散漫的討論...

O（N）表示取爲工作完成可以通過一些恆定量的時間加上N個某些功能被合理地近似的時間 - 在輸入出頭的數量 - 對於N巨大值：

• O（N）表示的時間爲c + XN，其中c是一個架空固定而x是每出頭的處理時間，
• 爲O（log N）表示時爲c + X（日誌 N），
• O（N ）表示時間爲c + X（N ），
• O（N！）表示時間點是c + X（N！）
• O（N ^Ñ）表示時間爲c + X（N ^ñ）
• 等。

同樣，在你的例子有輸入的數量沒有提到，並且循環迭代是固定的。我可以看到它是如何說它是O（1），即使有10個輸入「somethings」，但考慮：如果你有一個函數能夠處理任意數量的輸入，然後決定你只會使用它在你的應用程序中，只有10個輸入和硬編碼，你顯然沒有改變函數的性能特徵 - 你剛剛鎖定在N輸入曲線上的一個點上 - O複雜性在硬編碼之前必須仍然有效之前是有效的。儘管N爲10的數量很小，除非你有一個可怕的大O複雜度，如O（N ^N），常數c和x在描述整體性能方面更重要比它們對N的巨大值（其中大O符號的變化通常對性能的影響要比改變c甚至x更有影響 - 當然這是大O分析的全部要點）。