为什么选择排序，气泡或插入排序的效率据说是n ^ 2而不是n（n-1）/ 2 [英] Why efficiency of selection sort or Bubble or Insertion sort is said to be n^2 and not as 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 strong>

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²)

这篇关于为什么选择排序，气泡或插入排序的效率据说是n ^ 2而不是n（n-1）/ 2的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！