这个算法的效率是多少

Question

以下算法的大O值是多少？为什么这是价值？

algorithm A (val array <ptr to int>) 
    1 n = 0 
    2 loop (n < array size) 
    1 min = n; 
    2 m = n; 
    3 loop (m < array size) 
     1 if (array[m] < array[min]) 
      1 min = m; 
    4 swap(array[min],array[n]); 
    3 n = n + 1 

我回答了O（n^2）我正确吗？至于我如何得出这个结论，内循环执行n次，其中n =数组大小，外循环执行n次，其中n是数组大小n * n = n^2

Answer 1

是的！你是对的！

这是选择排序算法。其Θ（n^2）更精确。

编辑：为什么它的价值？

你拿第一个元素。将其与所有其他元素进行比较，以便在数组中找到最小值并将其置于首位。迭代：n。 你拿第二个元素。将其与数组的其余部分进行比较，然后在该部分中找到最小值（整个数组中的最小值）并将其放在第二位。迭代：n-1。 对于最后一个元素以这种方式继续，迭代：1.

总= n + n-1 + ... +1 = n（n + 1）/ 2。那是O（n^2）。

Answer 2

这就是所谓的“称为Selection sort，事实上它具有O（n ）的复杂性。