为什么选择排序的最佳时间复杂度是O(n^2),而插入排序和冒泡排序的最佳时间复杂度却是O(n)?它们的平均时间相同。我不明白为什么最佳时间不同。希望能得到一些帮助。
选择排序需要搜索最小值并将其放在第一次迭代中的第一个位置。在第二次迭代中,您必须在数组的非排序部分中搜索最小值并将其放置在第二个位置,以此类推......
只有在迭代到非排序部分的末尾后,您才知道哪个元素是最小的。即使数组已经排序,您也必须迭代到末尾。然后,您可以确定找到了最小值,并将其放置在正确的位置(已排序部分的末尾)
因此,第一次迭代需要n步来查找最小值。 第二次迭代需要n-1步来在未排序部分中找到最小值 ...... 最后一次迭代需要1步来在未排序部分中查找最小值。
完成这些步骤后,您将拥有一个已排序的数组(即使它之前是已排序的)。选择排序不会通过线性时间算法检查数组是否已排序。选择排序重复搜索最小值。这就是选择排序的工作方式。
当您反复搜索最小值时,需要n+(n-1)+...+1步骤,因此您得到(n²+n)/2,这是O(n²)