下面這段代碼的漸近時間複雜度是多少？

Question

你如何拿出大O符號？

float sum = 0 ; 
    for (int i = 1; i < n ; i++) 
    { 
    sum + = A[i]; 
    } 
    cout << sum; 

Answer 1

很好，你問這個。我剛剛在課堂上講過這個問題，並提出了同樣的問題。大O符號用於描述算法的效率和複雜程度。 O（1）是一個在同一時間執行的算法。這是最有效的算法類型。例如

bool bigO(String[] big) 
{ 
if(big[0] == null) 
{ 
    return false; 
} 
return true; 
} 

還有O（N）將取決於輸入的大小。例如，

bool bigO(String[] strings, String value) 
{ 
for(int i = 0; i < strings.Length; i++) 
{ 
    if(strings[i] == value) 
    { 
     return true; 
    } 
} 
return false; 
} 

正如您所看到的，根據輸入的不同，您可能需要更長的時間才能執行此操作。如果字符串長度很小，它會很快，但如果長度很長，則需要一段時間。

然後是O（N^2）。這涉及到自身內部的多個循環。它可以是O（N^3），取決於你嵌套迭代的深度。例如

bool bigO(String[] strings) 
{ 
for(int i = 0; i < strings.Length; i++) 
{ 
    for(int j = 0; j < strings.Length; j++) 
    { 
     if(i == j) 
     { 
      continue; 
     } 

     if(strings[i] == strings[j]) 
     { 
      return true; 
     } 
    } 
} 
return false; 
} 

現在看看你的算法，你認爲你的是什麼？ 如果你說O（N）你是對的。大O表示法取決於算法的效率。效率可以取決於 CPU（時間）的用法， ，存儲器使用 ，磁盤使用率 和網絡使用情況

Answer 2

在這一段代碼，這將影響到運行時間的唯一參數是n（的實際值因爲浮點加法的時間並不取決於操作數值 - 至少作爲第一個近似值），所以它們並不重要。所以運行時間被分析爲n的函數。

我們有兩個任務和一個輸出語句（sum= 0,i= 1,cout sum）執行一次。我們也看到一個循環，正好採取n-1次;它執行比較，兩個整數加法和一個跳轉（i < n,i++，sum+= A[i]，for）。

假設所有的原始操作都需要一定的時間，我們可以得出結論：對於兩個常量A和B，運行時間恰好爲A + B.n。

以漸近的方式（即當n變大時），您只關心該函數的整體行爲。所以你只要看看統治術語A.n，你甚至隱藏了常數A。這就是爲什麼你說運行時間被稱爲線性時間O(n)。