这个算法的效率是多少？

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。

- dave

---

这是作业吗？如果是，请标记为作业。 - PengOne

不，我只是在做一本书上的练习。至于我是如何得出结论的，内部循环执行n次，其中n为数组大小，而外部循环执行n次，其中n为数组大小，n*n = n^2。 - dave

Answer 1

这就是所谓的 选择排序，它的时间复杂度的确为 O(n²)。

- UncleAli

Answer 2

是的！你说得对！

这是选择排序算法。 更准确地说，它的时间复杂度为Θ(n^2)。

编辑：为什么它的值是Θ(n^2)?

首先取第一个元素。将其与数组中的所有其他元素进行比较，找到最小值并将其放置在第一位置。迭代次数为n。 取第二个元素。将其与数组的剩余部分进行比较，找到该部分的最小值（整个数组的第二小值）并将其放置在第二位置。迭代次数为n-1。 以此类推，对于最后一个元素，迭代次数为1。 总迭代次数 = n + n-1 + … + 1 = n(n+1)/2。即O(n^2)。

- Priyank Bhatnagar