泡泡排序的复杂性

Question

我在很多地方看到过,冒泡排序的复杂性是O(n ²).

但是怎么会这样呢,因为内环应该总是运行ni次.

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