java - 冒泡排序的复杂性

Question

我在很多地方看到，冒泡排序的复杂度是O(n²)。

但这怎么可能呢，因为内部循环应该总是运行 n-i 次。

for (int i = 0; i < toSort.length -1; i++) {
            for (int j = 0; j < toSort.length - 1 - i; j++) {
                if(toSort[j] > toSort[j+1]){
                    int swap = toSort[j+1];
                    toSort[j + 1] = toSort[j];
                    toSort[j] = swap;
                }
            }
        }

Answer 1

n-i 的“平均”值是多少？ n/2

所以它在 O(n*n/2) 中运行，这被认为是 O(n²)