示例 12 来自大 O 表示法的字符串的所有排列为什么第 7 行和第 10+11 行需要 O(n) 时间 - 破解编码面试

Question

不明白为什么执行第7行和第10+11行需要O(n)的时间

对于第 7 行，是否直接执行制作字符串，其中 1) 打印字符串的操作（例如计算机内部必须在屏幕上打印 a 然后 b 然后 c）是 O(n) 或是因为 2) 对于所有排列，我们打印了不同的 System.out.println(prefix) 吗？但是如果它的 1) 是否意味着每个 print 语句在每个函数中都是 O(n)？如果是 2) 为什么这部分不是 n!在 O(n*n!) 中，因为这是与第 5-14 行同时完成的，用于字符串的每个可能排列。

同样，第 10+11 行是因为当 java 连接时，它通过创建一个字符串来这样做，该字符串从不同的子字符串中将每个字母 1 乘 1 以创建新连接的字符串？

void permutation(String str){
   permutation(str,"");
}

void permutation(String str, String prefix){               // line 5
  if(str.length()==0){
    System.out.println(prefix);                            // line 7
  } else{
    for(int i=0;i<str.length();i++){
      String rem=str.substring(0,i)+str.substring(i+1);    // line 10
      permutation(rem,prefix+str.charAt(i));               // line 11
    }
  }
}                                                          // line 14

Answer 1

首先，您需要定义 n even 是什么。此 cas 中的一个合理定义是 n 是原始输入的大小 str（因为这是会变化并影响性能的主要维度）。

第 7 行中的打印 prefix 很容易被认为是 O(n) 因为 str.length == 0 为真，前缀必须与 str 大小相同（即它的长度为 n) 并且打印 n 个字符需要（渐近地）n 个时间单位（打印更多需要更多时间）。

这是否意味着每个 System.out.println 都是 O(n)？好吧，不。因为不是每个 System.out.println 都会有可变大小的输入。 System.out.println("Hello") 是 O(1)，因为无论周围发生什么，它总是需要相同的时间（至少在对大 O 重要的粒度上）。

行 10 是 O(n) 因为它将复制 n-1 个字符（这将减少到 O(n)，因为 big-O 不关心像 -1).

我的 big-O 时间太久远了，现在无法真正计算第 11 行，抱歉。我会留给其他人回答。

在此要牢记的重要警告是，big-O 是一个 big 概括，并且（有意）掩盖了很多细节。

O(1) 的一个动作可以 慢得多 或 快得多 比另一个也需要 O(1) 的动作，因为 常数因子被忽略。

因此仅仅因为“System.out.println 打印 n 个字符是 O(n)”并不意味着它很慢：它可以非常快并且在许多情况下打印 1、3、5 或即使是 1000 个字符也几乎小得无法估量。但是对于 big-O 表示法，唯一重要的是 大值 n 它将大致线性增长。

Answer 2

显然第 11 行没有 O(n) 成本。

实际上，成本是T(n) = (n-1)!（对于每个字符再次运行）。

你可以写痕迹很明显：

static int permutation(String str){
    return permutation(str,"");
}

static int permutation(String str, String prefix){
    if(str.length()==0){
        System.out.println(prefix);
        return 1;
    } else{
        int cost = 0;
        for(int i=0;i<str.length();i++){
            String rem=str.substring(0,i)+str.substring(i+1);
            int c = permutation(rem,prefix+str.charAt(i));
            System.out.printf("LINE 11 cost: %d (current size %d)%n", c, str.length());
            cost += c;
        }
        return cost;
    }
}

public static void main(String[] args) {
    System.out.printf("%nTOTAL COST: %d%n", permutation("ABCDE"));
}

有输出

...
LINE 11 cost: 1 (current size 1)
LINE 11 cost: 1 (current size 2)
EDCBA
LINE 11 cost: 1 (current size 1)
LINE 11 cost: 1 (current size 2)
LINE 11 cost: 2 (current size 3)
LINE 11 cost: 6 (current size 4)
LINE 11 cost: 24 (current size 5)

TOTAL COST: 120

(permutation(str) 需要 O(factorial(str.length())) 时间)

注意：如果考虑字符串连接，则不必考虑 O(n * n!)，因为 Java 有一个 Strings 缓存。另一方面，如果您考虑打印字符串的时间，那么是的，它是 O(n * n!)，因为每个字符必须打印总共 n * n! 个字符（加上 EOL 等）。

示例 12 来自大 O 表示法的字符串的所有排列为什么第 7 行和第 10+11 行需要 O(n) 时间 - 破解编码面试

Example 12 All Permutations of a string from Big O notation why line 7 and line 10+11 take O(n) time - Cracking the Coding Interview

java

algorithm

big-o