最大算法的复杂性

Question

我有一个像这样的基本最大算法：

for(int i = 1; i < a.length; i++){
    if(a[i-1]>a[i]){
        //switch a[i-1] with a[i]
        int temp = a[i-1]; a[i-1]=a[i]; a[i] = temp;
    }
}

任务是找出切换发生的平均次数？ 答案应该是

log(n)

，但我不明白怎么做。

因此，最好的情况会发生 0 次（如果数组已经排序），最坏的情况会发生

(n-1)

次（如果按降序排序）。 我尝试对 n 个数字进行随机排列并找到平均值，但我发现平均开关数量几乎开始攀升至大约 n。有没有人可以向我解释这种复杂性，我为此绞尽脑汁太久了。

提前致谢

Answer 1

您的算法似乎是用于对数组升序进行排序的冒泡排序。 这是问题线程，它已经解释了冒泡排序时间复杂度是如何工作的。 如何计算冒泡排序时间复杂度