选择排序的最佳时间复杂度
为什么选择排序的最佳案例时间复杂度为O（n^2），而插入排序和冒泡排序为O（n）？他们的平均时间是一样的。我不明白为什么最佳案例时间不同。如果你能帮忙，我将不胜感激。
共有1个答案
对于选择排序，您必须搜索最小值，并在第一次迭代中将其放在第一位。在第二次迭代中，您必须在数组的未排序部分搜索最小值，并将其放在第二位，以此类推。。。
在迭代到未排序部分的末尾后，您只知道哪个元素是最小的。即使数组已排序（！）你必须迭代到最后。然后您就可以确定您找到了将其放在正确位置的最小值（在已排序部分的末尾）
因此，第一次迭代需要n个步骤才能找到最小值。第二次迭代需要n-1个步骤来查找未排序部分中的最小值。。。最后一次迭代需要一个步骤来查找未排序部分中的最小值。
完成这些步骤后，您将得到一个已排序的数组（即使它之前已排序）。选择排序不会检查数组是否已按线性时间算法排序。选择排序重复搜索最小值。这就是选择排序的工作方式。
当您重复搜索最小值时，需要n（n-1）。。。所以你得到了O（n²）中的（n（n 1））/2=（n²n）/2
-
在这种情况下，复杂度不应该像O（n）=n*[（n-1）（n-2）......（n-（n-1））]那样，对于外环的n次中的每一次，内环运行的差分步长逐渐减小由一。这样O（n）就等于（n^3-n^2）/2。我的方法有什么问题？
-
我必须找到在c程序中输入最佳情况的快速排序的时间复杂度
-
我有一个关于计算时间复杂度的非常普遍的问题（大O符号）。当人们说QuickSort最差的时间复杂度是O（n^2）（每次都选择数组的第一个元素作为轴心，并且数组是反向排序的）时，他们考虑了哪个操作来获得O（n^2）？人们会计算if/else语句所做的比较吗？或者他们只计算其进行的互换的总数？一般来说，你如何知道计算大O符号需要计算哪些“步骤”。 我知道这是一个非常基本的问题，但我已经阅读了谷歌上几乎
-
让我们以合并排序的实现为例 a） 这种合并排序的时间复杂度是。并行化（1）和（2）会带来实际收益吗？从理论上讲，在对它们进行并行化之后，似乎最终也会出现。但实际上我们能得到什么好处吗？ b） 这种合并排序的空间复杂度是。但是，如果我选择使用链表执行就地合并排序（不确定是否可以合理地使用数组），空间复杂性是否会变得，因为您必须考虑递归堆栈帧大小？既然它不能超过64，我们能把当作常数吗？我可能在几个地
-
null
-
我已经学习了递归快速排序，最佳情况需要O（nlogn），最坏情况需要O（n^2）。但我试图找到迭代快速排序的时间复杂度。我知道最好的情况是O（nlogn）和O（n^2）。但我不会为最好的情况辩护。我正在学习本教程 https://www.techiedelight.com/iterative-implementation-of-quicksort/ 假设我们有15个元素，使枢轴索引位置始终处于中间