有人可以幫我解決這個演算法的時間復雜度嗎？查找最長的回文子串是 leetcode 的一項任務（https://leetcode.com/problems/longest-palindromic-substring/）。我相信這是 O(n3)，但是如何計算呢？我的方法是： for 回圈進行 s.length 次（稱為n），內部回圈，在字串由相等的字符組成的更糟糕的情況下，將擴大視窗 n 次，因此 O(n2)。但是對于 O(n^2) 來說，作業時間似乎很大。這是代碼：
public String longestPalindrome(String s) {
if (s.length() == 1) {
return s;
}
String max = "";
for (int i = 0; i < s.length() - 1; i ) {
int lpointer = i;
int rpointer = i 1;
while (rpointer < i 3) {
int t = rpointer;
System.out.println(lpointer " " rpointer);
while (lpointer >= 0 && rpointer < s.length() && s.charAt(lpointer) == s.charAt(rpointer)) {
lpointer--;
rpointer ;
}
String temp = s.substring(lpointer 1, rpointer);
max = max.length() < temp.length() ? temp : max;
rpointer = t 1;
lpointer = i;
if (rpointer == s.length()) {
break;
}
}
}
return max == "" ? String.valueOf(s.charAt(0)) : max;
}
非常感謝任何幫助！
uj5u.com熱心網友回復：
我會說你的演算法是 O(n2) 即使你有三個回圈：
for 回圈的時間復雜度很簡單：你有一個長字串n的迭代。n內部 while 回圈有點復雜：我注意到在內部 while 回圈之外，兩個游標總是與1or不同2。我想那是因為你想檢查均勻和不均勻的回文。這意味著對于 for 回圈的每次迭代，內部 while 回圈只運行兩次。此外，內部 while 回圈可以最大運行字串長度的一半，因為它在兩個方向上進行搜索。這導致兩個 while 回圈的復雜度為2 * n/2equals n。因此n*n導致 O(n2)。
盡管如此，除了時間復雜性之外，與平均提交相比，您的代碼運行速度非常慢（ >700ms ）。通過一些優化，我能夠重現一個只有15ms 運行時間的 O(n2) 演算法。它幾乎使用了您的嘗試。唯一的主要區別是，它使用兩個不同的單獨回圈，而不是使用兩個內部 while 回圈來區分偶數和奇數：
public static String longestPalindrome(String s) {
if (s.length() <= 0) return "";
char[] chars = s.toCharArray();
int longest = 0;
int iLongest = 0;
for (int i = 0; i < chars.length; i ) { //position to start from
if (longest == chars.length || (chars.length - 1 == longest && ((chars.length % 2 != 0 && longest % 2 == 0) || i - 1 > longest / 2))) break; //skip useless iterations
//uneven
for (int j = 0; j <= (chars.length - 1 - i < i ? chars.length - 1 - i : i); j ) { //max length possible in both directions
if (chars[i j] == chars[i-j]) {
int nLongest = j*2 1;
if (nLongest > longest) {
longest = nLongest;
iLongest = i;
}
} else break;
}
//even
for (int j = 0; j <= (chars.length - 1 - i < i ? chars.length - 1 - i : i - 1); j ) {
if (chars[i j] == chars[i-j-1]) {
int nLongest = (j 1)*2;
if (nLongest > longest) {
longest = nLongest;
iLongest = i;
}
} else break;
}
}
int start = iLongest - ((longest % 2 == 0 ? longest : longest - 1) / 2);
int stop = iLongest ((longest - 1) / 2);
return s.substring(start, stop 1);
}
希望能回答你的問題。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/498188.html
上一篇：最大化Task的數量，使第一個Task的開始時間總是最早的
下一篇：C#中二維陣列的方差和平均值