递归算法的时间复杂度

Question

我有以下内容：

public static int[] MyAlgorithm(int[] A, int n) {
    boolean done = true;
    int j = 0;
    while(j <= n - 2) {
        if(A[j] > A[j+1]) {

            int temp = A[j + 1];
            A[j + 1] = A[j];
            A[j] = temp;

            done = false;
        }
        j++;
    }
    j = n - 1;
    while(j >= 1) {
        if(A[j] < A[j-1]) {
            int temp = A[j - 1];
            A[j - 1] = A[j];
            A[j] = temp;
            done = false;
        }
        j--;
    }

    if(!done)
        return MyAlgorithm(A, n);
    else 
        return A;
}

这实质上是对长度为 'n' 的数组 'A' 进行排序。然而，在试图弄清楚这个算法的时间复杂度之后，我把运行圈了起来。如果我看一下第一个 while 循环，循环中的内容将执行 'n-2' 次，从而使其成为 O(n)。第二个 while 循环执行 'n-1' 次，因此使其成为 O(n)，前提是我们已经删除了两个函数的常量。现在，这个算法的递归部分又让我失望了。

递归看起来是尾递归的，因为它之后没有调用任何其他东西。在这一点上，我不确定尾递归的递归是否与这个时间复杂度有任何关系......如果这真的是一个 O(n) 这是否一定意味着它也是 Omega(n)？

如果有任何假设，请更正我所做的任何假设。任何提示都会很棒！

Answer 1

这是O(n²)。

这是因为每次递归时，您都会将整个数组迭代两次。向上一次（将最高答案冒泡到顶部）和一次向下（将最低答案冒泡到底部）。

在下一次迭代中，您还有另一个 2n。但是，我们知道最顶层和最底层的元素是正确的。因此我们知道我们有 n-2 个未排序的元素。当它重复时，您将再对 2 个元素进行排序，依此类推。如果我们想找到迭代次数 "i"，那么我们求解 n - 2i = 0. i = n/2 次迭代。

n/2 次迭代 * 每次迭代 2n 次操作 = n² 次操作。

编辑：尾递归并不能真正帮助时间顺序，但它确实有助于某些语言的内存处理。我不能确切地说出它是如何工作的，但它以某种方式显着减少了所需的堆栈 space。

此外，我对此有点生疏，但 O 表示法表示最差情况，而 Omega 表示法表示最佳情况。这是 Omega(n)，因为最好的情况是它迭代数组两次，发现所有内容都已排序，并且不递归。

Answer 2

在你的例子中，递归关系是这样的：

T(n) = T(n) + n.

但是如果我们假设最大的没有。在每种情况下都会结束。我们可以近似：

T(n) = T(n-1) +n

T(n-1) = T(n-2) + n-1

t(n-2) = T(n-3) + n-2

T(n) = T(n-2) + n-1 +n

T(n) = T(n-3) + n-2 + n-1 + n

T(n) = T(n-k) + kn -k(k-1)/2

如果 n-k = 1

那么 k = n+1 替换那个

T(n) = T(1) + n(n+1)-(n+1)(n)/2

阶 O(n^2)

也是最小号将在开头结束，所以我们也可以近似。

T(n) = T(n-2) +n

仍然是 O(n^2)

如果删除该近似值，我们将无法准确估计何时完成将是真实的。但在这种情况下我们可以确定最大的不每次迭代后总是会在最后结束，而最小的会在开始时结束，因此不会对 0 和 n-1 做任何事情。

我希望这能帮助你理解为什么 n^2。

递归算法的时间复杂度

Time complexity of algorithm with recursion

java

time-complexity

data-structures