大插入排序算法：迭代和递归

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)时间。您不可能通过从递归切换到迭代实现来减少算法的运行时间，反之亦然。尽管如此，不是。

如何确定运行时间为O(n^2)。迭代解决方案更容易也更明显。一般来说，如果嵌套for -loops而没有任何特定的中断条件，并且运行的是线性元素的一部分，则运行时间是二次的。让我们进一步分析一下。 for (int i = 1; i < list.length; i++)的条件会评估为true多少次？答案是n-1，因为你从第二个元素直到结束。例如，如果n=5，则条件将为true，对于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中，因此运行时间为O(n^2)。

现在对第二个实现的分析可能会因为递归而显得复杂一点，但实际上并没有太大的不同。内循环的逻辑for (i = j; i > 0 && array[i - 1] > temp; i--)几乎是一样的，因为它被执行一次，当j = 1，当j = 2等两次时，我们将多次调用该方法递归？再次n - 1次，因为第一次调用是j = 1，因此j < n（假设n很大），然后调用​​。现在j = 2再小于n，所以我们将递归调用该函数，直到j == n，那么确切地说是n - 1次。鉴于内部循环嵌套在O(n)中，我们得到相同的迭代次数，即1 + 2 + 3 + ... + (n-1)导致O(n^2)再次。

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