这里我有两个插入排序算法。我很难找到这两种插入排序形式的大 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);
}
}
最佳答案
是的,你是对的,两种实现都需要 O(n^2)
时间。您不可能通过从递归实现切换到迭代实现来减少算法的运行时间,反之亦然。不过,这不适用于空间使用情况。
如何确定运行时间为O(n^2)
.迭代解决方案更容易和更明显。一般来说,当你嵌套了 for
-没有任何特定中断条件的循环,并且您正在运行一部分线性元素,运行时间是二次的。让我们进一步分析它。 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 很大),然后调用 recursiveSort(array, n, j + 1);
.现在j = 2
再次小于 n
, 所以我们将递归调用函数直到 j == n
,所以正是n - 1
次。鉴于内部循环嵌套在 O(n)
中,我们得到相同的迭代次数,即1 + 2 + 3 + ... + ( n-1 )
导致 O(n^2)
再次。
因此我们非正式地证明了这两种算法具有相同的渐近运行时间。在这种情况下我们可以认为它们是等价的吗? 否。这是因为每个递归调用都会在堆栈上保留额外的空间,这意味着递归解决方案需要 O(n)
空间,而迭代的 O(1)
.从这个意义上说,我们可以说迭代解决方案更好,这通常是这种情况,但递归解决方案可能更具可读性(这里不是这种情况)。
关于java - 插入排序算法大o : iterative and recursive,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34235195/