java - for循环java中递归的时间复杂度

Question

你好，我遇到了这个问题。我尝试在几个堆栈溢出帖子、谷歌和 youtube 的帮助下解决这个问题三天，但我无法解决这个问题。

我的问题是。我如何获得 T(N) = ？对于烫发(1)。我猜它是 O(n^2) 甚至更糟，因为以下原因。我的 for 循环取决于变量 n，我的内部递归需要 n+1，所以这将是 n*(n+1) ~ n^2。但是我如何完成这个程序并证明这一点呢？我知道我可以忽略所有常量因素，如加法等，但如果有人花时间解释代码中的每个时间单位成本并总结它直到我们有一个递归方程，我会很高兴。

为了获得每一个排列，我们将 perm(1) 更改为 perm(0)。1) 如果我们排列 n 个数字，我们有多少次调用2) 如果 n 变得非常大，单个排列平均省略了多少调用。

解释。我们给这个程序 n 个数字来排列。如果我们也想置换 0，我们调用 perm(0)，否则我们调用 perm(1)。

private void perm(int i) { // permute from index i; 1 or 0(all permuts).
    if (i >= max) put();  // one permutation finished, max = n-1
    else {
        for (int j = i; j <= max; j++) { // everyone in front
            swap(i, j);               // swap
            perm(i + 1);               // and recursion
        }
        int h = a[i];                 // restore Array
        System.arraycopy(a, i + 1, a, i, max - i); // shift left
        a[max] = h;
    }
} // end perm

private void swap(int i, int j) {   // swap a[i] <-> a[j]
    if (i != j) {
        int h = a[i];
        a[i] = a[j];
        a[j] = h;
    }
} // end swap

private synchronized void put() {   // give over to array
    mayread = true;                 // read a (array)
    notify();                      // notify the other Thread
    try {
        if (a != null)
            while (mayread) wait();    // non busy waiting
    } catch (InterruptedException e) {
    }
} // end put

我的最后一个问题。当我们在 for 循环中调用 swap(1,1) as j=i 或 swap(2,2) 以及之后的递归时，到底发生了什么。

Answer 1

swap 是 O(1)。

perm 执行一个 max-i+1 迭代循环，然后在每次迭代中执行 perm(i+1)。然后，毕竟，它执行了 max-i 项的数组复制。

我们称max为n。

• perm(1) 执行循环 n 次
• perm(2) 执行循环 n-1 次
• perm(3) 执行循环 n-2 次

等等……

这导致 n*(n-1)*(n-2)*...*1 迭代。 O(n!)

此外，swap(1, 1) 什么也不做。