最大算法的复杂性

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

这不是“最大算法”。这是冒泡排序或插入排序的单次滑动，其中第一次交换的概率为 1/2，最后一次交换的概率接近 1（因为比较不是独立的）。

如果我猜测哪种最大算法可以给出 O(log N) 交换的平均复杂度，它可能意味着更新累积最大值时预期的情况数。

在该算法中，最坏情况仍然是 O(N)，最好情况是 O(1)。无论如何，在数组的早期很可能会有一些大的值，这将阻止进一步的交换。我没有证据，但枚举一些小数组（大小 4、大小 8）显示了交换次数的 O(log2(N)) 趋势：

八度音阶：

mean(sum(diff(cummax(perms(1:4)')) ~= 0))+1
ans = 2.0833
octave:2> mean(sum(diff(cummax(perms(1:8)')) ~= 0))+1
ans = 2.7179

尝试

perms(1:16)

是不可行的（有20922789888000种排列）；但这当然可以使用蒙特卡罗算法模拟更大的数组。

Answer 2

交换发生的平均次数为 log𝑛 的说法是错误的。然而，如果我们计算交换不发生的平均次数，最终结果为 O(log𝑛)。

证明

假设数组的长度为 𝑛，并且具有 0 到 𝑛−1（包括）之间的不同整数值。

最大交换次数为𝑛−1。

在第一次迭代中不进行交换的概率是 1/2

对于第二次迭代，我们可以进行如下推理：

假设前两个值的分布是均匀分布，因此预期最小值为 ~(1/3)𝑛，预期最大值为 ~(2/3)𝑛。由于第一次迭代后最大值必须位于索引 1 处，因此我们预计不与数组中的下一个值交换的概率为 1/3。

类似地，对于第三次迭代，我们可以说有 1/4 的概率不交换...

这样一直持续到最后一次迭代，我们将在索引

i-1

处得到最大值（最大概率），或者最大值已经位于索引

i

处的微小概率。属于后者的病例数为总病例数的 1/𝑛^th。

因此，预期的非掉期总数是一个包含 𝑛−1 项的序列：

      1/2 + 1/3 + ... + 1/𝑛

如果我们在其前面加上一个额外的项 1/1，那么这就是渐近逼近 log𝑛 的调和级数。对于渐近复杂性，缺失项 1 不相关。

因此我们可以得出结论，no(!) 交换的次数，其复杂度为 O(log𝑛)。交换次数的复杂度为 O(𝑛−1−log𝑛)，即 O(𝑛)。

Answer 3

您的算法似乎是冒泡排序，用于按升序对数组进行排序。

这是已经解释了冒泡排序时间复杂度如何工作的问题。

如何计算冒泡排序的时间复杂度