3

这是我写的一个 SelectionSort 例程。我的复杂性分析是否正确？

public static void selectionSort(int[] numbers) {

    // Iterate over each cell starting from the last one and working backwards
    for (int i = numbers.length - 1; i >=1; i--)
    {
        // Always set the max pos to 0 at the start of each iteration
        int maxPos = 0;

        // Start at cell 1 and iterate up to the second last cell
        for (int j = 1; j < i; j++)
        {
            // If the number in the current cell is larger than the one in maxPos,
            // set a new maxPos
            if (numbers[j] > numbers[maxPos])
            {
                maxPos = j;
            }
        }

        // We now have the position of the maximum number. If the maximum number is greater
        // than the number in the current cell swap them
        if (numbers[maxPos] > numbers[i])
        {
            int temp = numbers[i];
            numbers[i] = numbers[maxPos];
            numbers[maxPos] = temp;
        }
    }
}

复杂性分析

外循环（比较和分配）：2 次操作执行 n 次 = 2n 次操作

分配 maxPos：n 个操作

内循环（比较和分配）：2 次操作执行 2n^2 次 = 2n² 次操作

数组元素的比较（2 个数组引用和一个比较）：3n² 操作

分配新的 maxPos: n² ops

数组元素的比较（2 个数组引用和一个比较）：3n² 操作

赋值和数组引用：2n² 操作

赋值和 2 个数组引用：3n² 操作

赋值和数组引用：2n² 操作

原始操作总数

2n + n + 2n² + 3n² + n^2 + 3n² + 2n² + 3n² + 2n² = 16n² + 3n

通向大哦(n²)

这看起来正确吗？特别是当涉及到内部循环和里面的东西时......

4

2 回答 2

2

是的，O(N 2 ) 是正确的。

编辑：就“从第一原则”而言，很难准确猜测他们可能想要什么，但我猜他们（本质上）正在寻找证据（或至少是迹象）的东西) 满足 big-O 的基本定义：

存在正常数c和n 0使得：

0 ≤ f(n) ≤ cg(n) 对于所有 n ≥ n 0。

因此，找到 16N 2 +3N之后的下一步是找到 n 0和 c的正确值。至少乍一看， c 似乎是 16，而 n 0，-3，（可能被视为 0，没有实际意义的负数元素）。

于 2012-05-02T17:11:25.583 回答
1

通常，将实际操作相加是没有意义的（也是不正确的），因为操作需要不同数量的处理器周期，其中一些从内存中取消引用值需要更多时间，然后因为编译器优化代码而变得更加复杂，然后你有诸如缓存位置之类的东西，所以除非你非常非常清楚地知道下面的一切是如何工作的，否则你就是在加起来苹果和橘子。您不能只是将“j < i”、“j++”和“numbers[i] = numbers[maxPos]”相加，就好像它们相等一样，而且您不需要这样做 - 出于复杂性的目的分析，恒定时间块就是恒定时间块。您没有进行低级代码优化。

复杂度确实是 N^2，但是你的系数没有意义。

于 2012-05-02T18:33:29.447 回答