为什么不是o(n^3),因为在每个for循环中,我们做2个循环,一个用于len1,另一个用于len2?
下面的解决方案是正确输出回文。但我很困惑。
以下是leetcode的解决方案:
public String longestPalindrome(String s) {
if (s == null || s.length() < 1) return "";
int start = 0, end = 0;
//Loop 1
for (int i = 0; i < s.length(); i++) {
//Loop 2
int len1 = expandAroundCenter(s, i, i);
//Loop 3
int len2 = expandAroundCenter(s, i, i + 1);
int len = Math.max(len1, len2);
if (len > end - start) {
start = i - (len - 1) / 2;
end = i + len / 2;
}
}
return s.substring(start, end + 1);
}
private int expandAroundCenter(String s, int left, int right) {
int L = left, R = right;
while (L >= 0 && R < s.length() && s.charAt(L) == s.charAt(R)) {
L--;
R++;
}
return R - L - 1;
}
你知道吗?
2条答案
按热度按时间368yc8dk1#
你可能会被
expandAroundCenter
跑两次。expandAroundCenter
函数为o(n)。它运行了两次,但是,它是按顺序运行的。所以它类似于o(2n),而不是o(n^2)。当在for循环中调用expandaroundcenter函数时:
T(n) = n x 2n = 2n^2
所以,时间复杂度是o(n^2)。eblbsuwk2#
论点很直截了当:
外环是
∈ O(n)
两个内部循环(调用expandAroundCenter(...)
)按顺序运行,而不是嵌套运行。因此,它们的复杂性可以加起来对于内部循环,最坏的情况是它从循环的中心扩展
String
向外,即。left
以及right
设置为n/2
. 在这种情况下,内部循环最多可以迭代n/2
-从那以后的几次left < 0
或者right >= n
. 因此,总的来说,内部循环是∈ O(n)
总的来说,我们得到了O(n) (outer loop) * 2 * O(n) (inner loops in sequence) ∈ O(n^2)
关于代码的一些注解:虽然可能,但在java中,在一行中声明多个变量是不常见的。因此
应该是
此更改只是代码样式的选择,对字节码没有影响。详见此帖。
单行语句周围的可选大括号绝对不能省略。如果我们以后想添加一行而忘记包含所需的大括号,那么这可能是一个令人讨厌的bug的来源。因此
应重新写入
变量名应该以小写字母开头(
L
->l
,R
->r
).变量应该有有意义的名称。
l
以及r
不是很有意义。因此,我建议进行以下重构:重命名参数
left
以及right
至leftStart
以及rightStart
重命名参数l
以及r
至currentLeft
以及currentRight