为什么说选择排序、冒泡排序或插入排序的效率是 n^2 而不是 n(n-1)/2

Question

假设我有一个降序数字数组（最坏情况）像：

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

现在如果我使用选择排序（这将按升序对它们进行排序）：

选择排序算法：

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（基本math) 但在我们的例子中 N 不是数组最后一个索引的大小，它是 size-1 所以这里 N 将是 N-1.

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

=> (N-1)(N-1+1)/2

=> N(N-1)/2

冒泡排序和插入排序也是如此。那么为什么这些排序算法的效率据说是 n^2 并注意 n(n-1)/2 ？

当 size=5 时，如果考虑 n^2，我们将得到 25，但考虑 n(n-1)/2 时，我们将得到 10？ Why/How n^2 在这里仍然被认为是效率？

Answer 1

在大 O 表示法中，只计算最重要的项，忽略常数系数：

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

Answer 2

你问题中的表述不够准确。不说是n²，而是Θ(n² )，即以与 n².

相同的顺序生长的东西

你上面的分析符合。对于足够大的 n:

n (n - 2) / 2 ≤ 2 n², 所以是 O(n²),

但n (n - 2) / 2 ≥ n² / 4,所以是Ω( n²).

Answer 3

在big-O表示法中，你总是取上限，从而取贡献越大的项，例如，n立方的次方大数将比n平方发挥更大的作用编号，因此您忽略了低阶项，因此在提到 big-o 表示法中的顺序时不要提及。

为什么说选择排序、冒泡排序或插入排序的效率是 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

sorting

algorithm

performance

big-o