为什么冒泡排序复杂度是O(n ^ 2)? [英] Why Bubble sort complexity is O(n^2)?

问题描述

据我了解，算法的复杂性是排序时执行的最大操作数.因此，冒泡排序的复杂度应该是算术级数的总和(从1到n-1)，而不是n ^ 2. 以下实现计算比较次数:

As I understand, the complexity of an algorithm is a maximum number of operations performed while sorting. So, the complexity of Bubble sort should be a sum of arithmmetic progression (from 1 to n-1), not n^2. The following implementation counts number of comparisons:

public int[] sort(int[] a) {
    int operationsCount = 0;
    for (int i = 0; i < a.length; i++) {
        for(int j = i + 1; j < a.length; j++) {
            operationsCount++;
            if (a[i] > a[j]) {
                int temp = a[i];
                a[i] = a[j];
                a[j] = temp;
            }
        }
    }
    System.out.println(operationsCount);
    return a;
}

包含10个元素的数组的输出为45，因此它是从1到9的算术级数之和.

The ouput for array with 10 elements is 45, so it's a sum of arithmetic progression from 1 to 9.

那么为什么冒泡排序的复杂度是n ^ 2，而不是S(n-1)?

So why Bubble sort's complexity is n^2, not S(n-1) ?

推荐答案

这是因为big-O表示法描述了算法的性质.扩展(n-1) * (n-2) / 2中的主要术语是n^2.因此，随着n的增加，所有其他术语变得无关紧要.

This is because big-O notation describes the nature of the algorithm. The major term in the expansion (n-1) * (n-2) / 2 is n^2. And so as n increases all other terms become insignificant.

欢迎您对其进行更精确的描述，但是出于所有意图和目的，该算法表现出的行为的顺序为n^2.这意味着，如果根据n绘制时间复杂度，则会看到一条抛物线的增长曲线.

You are welcome to describe it more precisely, but for all intents and purposes the algorithm exhibits behaviour that is of the order n^2. That means if you graph the time complexity against n, you will see a parabolic growth curve.

这篇关于为什么冒泡排序复杂度是O(n ^ 2)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！