java - 计算这个具体算法的时间复杂度

Question

public static String findLongestSubstring(String str) {
for (int len = str.length(); len >= 2; len--) {
    for (int i = 0; i <= str.length() - len; i++) {
        String substr = str.substring(i, i + len);
        int vowels = countVowels(substr);
        int consonants = len - vowels;
        if (vowels == consonants) {
            return substr;
        }
    }
}
return "";
}

private static int countVowels(String str) {
return str.replaceAll("[^AEIOUaeiou]+", "").length(); 
 }

发件人:problem

我的计算:

第一个循环有 (str.length - 1) 次旋转。第二个循环依赖于第一个循环，所以它是这样的: (0), [0, 1], [0, 1, 2] , ... , [0, 1 .., str.length - 2] 因此这是总共(仅第二个循环)1 + 2 + ... + N - 2 = (2N-3)^2/8 -1/8 ~ (2N)^2。如果我们让 N=str.length。在第一个循环中，我们有 (N-1) ~ N，因此总共有 ~N^3。但是我们必须假设在两个循环内，它是 O(1) 否则我们有 > O(N^3)?

但我认为这是不对的。

我们如何计算这样的时间复杂度？

Answer 1

假设 n 是 str 的长度，你得到:

• 外循环迭代 n - 1 次:O(n)
• 内部循环迭代 1 到 n - 1 次，所以平均 n/2 次:O(n)
• replaceAll() inside countVowels() 迭代 2 到 n 个字符，所以平均 n/2 + 1 次:O(n)
• 总计 O(n) * O(n) * O(n)，所以:O (n³)

^{注意:substring() 的性能取决于 version of Java ，因此它要么是 O(1)(早期的 Java)，要么是 O(n)(后来的 Java)。但是由于 O(1) + O(n) 和 O(n) + O(n) 是都是O(n)，对内部循环体的性能没有影响，这就是为什么上面的逻辑只考虑了replaceAll()的性能。}

---

更新

外部和内部循环组合的性能有三种计算方式，不包括主体中发生的情况:

1. O 数学:外循环是 O(n)，内循环是 O(n)，所以总计是O(n) * O(n) = O(n²)

2. 迭代数学:外循环迭代 n - 1 次，内循环迭代 n/2 次(平均) ，所以总数是 (n - 1) * (n/2) = n²/2 - n/2。由于只计算增长最快的因素，这意味着 O(n²)

3. 迭代求和:对内循环的迭代求和，即1 + 2 + ... + n-1。序列的总和可以计算为 count * average，平均值可以计算为 (min + max)/2。这意味着 average = (1 + n-1)/2 = n/2 和 sum = (n - 1) * (n/2)，这是与上面 #2 中得到的结果完全相同，所以它是 O(n²)

如您所见，O 数学更简单，因此选择它作为答案。