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)?
但我觉得这不对。
我们如何计算这样的时间复杂度?
最佳答案
假设n
是str
的长度,则得到:
外循环迭代次数:O(n)
内环迭代1到n - 1
次,因此平均n - 1
次:O(n)n / 2
在replaceAll()
内迭代2到countVowels()
个字符,因此平均n
次:O(n)
总计为O(n)*O(n)*O(n),so:O(n3)
注意:n / 2 + 1
的性能取决于version of Java,所以它要么是o(1)(早期java)要么是o(n)(后期java)。但由于O(1)+O(n)和O(n)+O(n)都是O(n),这对内环体的性能没有影响,这就是为什么上述逻辑只考虑了substring()
的性能。
更新
有三种计算外环和内环组合性能的方法,不包括在主体中发生的情况:
o数学:外环是o(n),内环是o(n),所以总数是o(n)*o(n)=o(n2)
迭代数学:外循环迭代replaceAll()
次,内循环迭代n - 1
次(平均),所以总数n / 2
因为只有增长最快的因素起作用,这意味着O(n2)
迭代和:对内部循环的迭代进行求和,即(n - 1) * (n / 2) = n² / 2 - n / 2
序列的和可以计算为1 + 2 + ... + n-1
,平均值可以计算为count * average
这意味着(min + max) / 2
,和average = (1 + n-1) / 2 = n / 2
,这与我们在上面2中得到的结果完全相同,所以它是o(n2)
正如你所看到的,o数学更简单,所以这就是为什么它被选为答案。
关于java - 计算此特定算法的时间复杂度,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/39620804/