插入排序算法的大o：迭代与递归

Question

这里我有两种插入排序算法。我很难找到这两种插入排序形式的大 O。我有一个迭代形式和一个递归形式。我说迭代形式是n^2而递归形式是n^2是不是错了。如果我错了，它们是什么，为什么？你是怎么得出这个答案的？

  public void iterativeSort(int[] list) {
        start = System.currentTimeMillis();
        for (int i = 1; i < list.length; i++) {
            count++;
            int temp = list[i];
            int j;

            for (j = i - 1; j >= 0 && temp < list[j]; j--) {
                list[j + 1] = list[j];
            }

            list[j + 1] = temp;
            finish += System.currentTimeMillis() - start;
        }

    }

    public static void recursiveSort(int array[], int n, int j) {
        finish += System.currentTimeMillis() - start;
        start = System.currentTimeMillis();
        if (j < n) {

            int i;
            count++;
            int temp = array[j];

            for (i = j; i > 0 && array[i - 1] > temp; i--) {
                array[i] = array[i - 1];
            }

            array[i] = temp;

            recursiveSort(array, n, j + 1);
        }
    }

Answer 1

是的，你说得对，两种实现都需要 O(n^2) 时间。您不可能通过从递归实现切换到迭代实现来减少算法的运行ning 时间，反之亦然。不过，这不适合 space 用法。

如何判断运行ning时间为O(n^2)。迭代解决方案更容易和更明显。通常，当您嵌套 for 循环而没有任何特定的中断条件并且您正在运行ning 通过一小部分线性元素时，运行ning 时间是二次方的。让我们进一步分析它。 for (int i = 1; i < list.length; i++) 中的条件将计算为 true 多少次？答案是 n-1，因为您是从第二个元素开始直到最后。例如，如果 n=5，条件将是 true for i = 1, 2, 3, 4（由于基于 0 的索引），恰好 n-1 次，在这个例子中意味着 4。现在如何内部循环条件多次计算为 true？在第一个运行上，它将执行一次，因为 i = 1 和 j = 0 并且在一次迭代后 j 将是 -1，这将打破条件。在第二次迭代中它将执行两次，在第三次迭代中执行三次等等，最多 n - 1 次。所以我们基本上得到的是总和 1 + 2 + 3 + ... + (n - 1)，你可以很容易地证明它等于 (n-1)n/2)。由于您在 big-O 中删除常量，因此运行ning 时间为 O(n^2).

现在第二个实现的分析可能因为递归的缘故显得复杂了一点，其实差别不大。内部循环 for (i = j; i > 0 && array[i - 1] > temp; i--) 的逻辑几乎相同，因为它在 j = 1 时执行一次，在 j = 2 时执行两次等等。我们将递归调用该方法多少次？再次 n - 1 次，因为第一次调用是 j = 1，因此 j < n（假设 n 很大），然后调用 recursiveSort(array, n, j + 1);。现在 j = 2 再次小于 n，因此我们将递归调用该函数直到 j == n，正好 n - 1 次。鉴于内部循环嵌套在 O(n) 中，我们得到相同的迭代次数，即 1 + 2 + 3 + ... + ( n-1 ) 再次导致 O(n^2)。

所以我们非正式地证明了两个算法具有相同的渐近运行ning时间。在这种情况下我们可以认为它们是等价的吗？没有。这是因为每次递归调用都会在堆栈上保留额外的 space，这意味着递归解决方案需要 O(n) space，而迭代解决方案需要 O(1)。从这个意义上说，我们可以说迭代解决方案更好，通常是这样，但递归解决方案可能更具可读性（这里不是这种情况）。

插入排序算法的大o：迭代与递归

Big o of insertion sort algorithm: iterative and recursive

java

algorithm

sorting

recursion

insertion-sort