計算大O

Question

我是編程新手，我想弄清楚如何計算算法的大O.例如：

int selectkth(int a[], int k, int n){ 
    int i, j, mini, temp; 
    for(i=0, i < k, i++){ 
     mini = i; 
     for(j = i+1; j < n; j++) 
     if(a[j] < a[mini]) 
     mini = j; 
     temp = a[i]; 
     a[i] = a[mini]; 
     a[mini] = temp; 
     } 
     return a[k-1]; 
    } 

我知道這裏有9個步驟發生，並且嵌套循環應該被放在一起。當我第一次嘗試時，我得到了O（n^2），但我不認爲這是正確的。有人可以解釋一下，如何以一種簡單的方式爲像我這樣的新手正確計算Big O？任何解釋都會幫助你或你自己的例子。謝謝:)

Answer 1

o（n^2）是正確的。代碼中運行時間最大的因素是兩個嵌套循環。其他的東西只是處理變量 - 你不需要擔心。這裏的大O實際上是k n = n n = n * 2 = O（n^2） 它是數組的長度。 k次

Answer 2

For outer loop, there k iteration 
for inner loop: 
For iteration #1 : n times array manipulation 
For iteration #2 : n - 1 times array manipulation 
. 
. 
For iteration #k : n - k times array manipulation 

total array manipulation = n + (n-1) + ..... + (n -k) 
= n(n+1)/2 - k(k+1) /2 
=~(n*2 - k*2) 

= ~(n*2) // if n is very very greater than k