有 Java 编程相关的问题?

你可以在下面搜索框中键入要查询的问题!

java大o插入排序算法:迭代和递归

这里有两种插入排序算法。我很难找出这两种插入排序形式的大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);
        }
    }

共 (1) 个答案

  1. # 1 楼答案

    是的,您是对的,这两种实现都需要O(n^2)时间。您不可能通过从递归实现切换到迭代实现来减少算法的运行时间,反之亦然。不过,这并不适用于空间使用

    如何确定运行时间为O(n^2)。迭代解更容易,也更明显。一般来说,如果嵌套了for循环,没有任何特定的中断条件,并且运行了一小部分线性元素,则运行时间是二次的。让我们进一步分析一下。在for (int i = 1; i < list.length; i++)中的条件将被评估为true多少次?答案是n-1,因为你从第二个元素一直到最后。例如,如果n=5,则条件将是trueFor i = 1, 2, 3, 4(由于基于0的索引),正好是n-1次,在本例中表示4。现在,内部循环条件将计算多少次true?在第一次运行时,它将被执行一次,因为i = 1j = 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)

    因此,我们非正式地证明了这两种算法具有相同的渐近运行时间。在这种情况下,我们能认为它们是等价的吗?strong>否。这是因为每个递归调用都会在堆栈上保留额外的空间,这意味着递归解决方案占用O(n)空间,而迭代解决方案占用O(1)空间。从这个意义上讲,我们可以说迭代解更好,这通常是事实,但递归解可能更具可读性(这里的情况并非如此)