java - 数组算法及其时间复杂度分析

Question

我应该分析这段代码并说明它的时间复杂度，但我无法理解代码本身的作用，它如何改变数组 a？

下面两个操作我也不明白: 1) foobar[a[i]]++; 所以你用数组 a 的元素替换 foobar 中的零？但是++ 有什么作用呢？

2) a[outPos++]=1; 这首先增加 outPos，并在整个 for 循环期间保持 a[0] 不变？

public static void foo(int[] a, int b) {
    int [] foobar = new int[b+1];
    for (int i = 0; i<foobar.length; i++)
        foobar[i]=0;
    for (int i = 0; i<a.length; i++)
        foobar[a[i]]++;
    int outPos = 0;
    for (int i=0; i<foobar.length; i++)
        for (int j=0; j<foobar[i]; j++)
            a[outPos++]=i;
}

就时间复杂度而言，我认为是 O(n^2)。前两个 for 循环以恒定时间运行。但是第三个嵌套循环最坏的情况在我看来是foobar最后一个元素很大，然后就是二次方了？

Answer 1

它是 Counting Sort 的一个实现,

其中a[]存放的是待排序的数组，b是a[]中的最大整数

foobar[] 是大小为 b

的计数数组

令 N = sizeof(a), M = b 为通用符号，

前两个循环:

1. 将计数数组初始化为零 O(M)
2. 计算元素，假设 a[] 中有 3 个 10，foobar[10] = 3，O(N)

棘手的第三个循环:

1. 外层循环，毫无疑问，O(M)
2. 内循环，您必须考虑 j 可以增加的总(最大)# 时间:即 Sum(foobar[]) = sizeof(a) = N，所以确实这个循环，在整个外循环迭代中，最多执行 N 次。 所以两个循环作为一个整体都是 O (N+M)，而不是直观上的 O(NM)

所以总复杂度是:O(N) + O(M) + O(N+M) = O(N+M)。

如果你发现第三个循环的复杂度难以理解，可以这样想:

这是一个零和游戏。如果一些 foobar[z] 很大，那么有很多 foobar[j] = 0 这几乎意味着跳过这样的 i 的内部循环.否则，所有 foobar[j] 都将处于平均大小。

很难分析i的每次迭代，但很容易分析整个内循环，因为我们知道foobar[]的总和是常数。