为什么选择排序，气泡或插入排序的效率据说是n ^ 2而不是n（n

本文介绍了为什么选择排序，气泡或插入排序的效率据说是n ^ 2而不是n（n-1）/ 2的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

假设我有一个降序数组（最坏的情况），例如：

Suppose I have an array of descending Numbers(Worst Case scenario) Like:

数字= {50,40,30,20,10}（大小= 5 ）

Nums = {50,40,30,20,10} (size = 5)

现在，如果我使用选择排序（它将按升序排序）：

Now If I use Selection sort (which would sort them in ascending):

选择排序算法：

for(i=0; i<=size-2; i++) { for(j=i+1; j<=size-1; j++) { if(Nums[i]>Nums[j]) { temp=Nums[i]; Nums[i]=Nums[j]; Nums[j]=temp; } } }

现在如果我们分析数字

(OuterLoopIndex Vs InnerLoopIndex): 1st Iteration: 0 - 1, 0 - 2, 0 - 3, 0 - 4 2nd Iteration: 1 - 2, 1 - 3, 1 - 4 3rd Iteration: 2 - 3, 2 - 4 4th Iteration: 3 - 4

现在如果将所有操作总数相加每次迭代它们都是 10 （4 + 3 + 2 +1），就像N个数字的总和，其公式为 N（N + 1）/ 2 （基本数学），但在我们的示例中，N不是数组最后一个索引的大小，即size-1，因此这里的 N 为 N-1 。

Now If add all the total number of operations in each iteration they are exactly 10 (4 + 3 + 2 + 1) Which is Like Sum of N numbers whose formula is N(N+1)/2 (basic math) but in our example here N is not the size its the last index of array which would be size-1 so here N would be N-1.

因此，如果将 N = N-1 替换为 N（N + 1）/ 2

Hence we would get something like this if substitute N=N-1 in N(N+1)/2

=> （N-1）（N-1 + 1）/ 2

=> N（N-1） / 2

气泡和插入排序也一样。那么为什么这些排序算法的效率据说是n ^ 2并注意n（n-1）/ 2呢？

Same goes for Bubble and Insertion sort. So why efficiency of those sorting algorithms is said to be be n^2 and note n(n-1)/2 ?

当size = 5时，如果我们考虑n ^ 2我们将得到25，而考虑n（n-1）/ 2时只有10。为什么/如何在这里n ^ 2仍然被认为是效率？

when size=5 we would get 25 if we consider n^2, but only 10 when considering n(n-1)/2 ? Why/How n^2 is still considered as efficiency here ?

推荐答案

在big-O表示法中，只有最重要的术语才有意义，并忽略常数系数：

In big-O notation only the most significant term counts, and constant coefficients are ignored:

O[n(n-1)/2] = O[n²/2 + n/2] = O[n²/2] = O(n²)