计算大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乘以n。

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