インタビューをコーディングするためのオンラインアルゴリズムソリューションをいくつか調べていますが、このアルゴリズムがO（n ^ 3）であると主張されている理由がわかりません。
警告：big-Oh表記は業界で悪用されていることを理解しています。O（n）を参照するときは、ほとんどの場所で学界以外で一般的であるように、アルゴリズムランタイムの上限を意味するためにその表記を使用しています。
最長の回文部分文字列を見つける。簡単な解決策は次のとおりです。
bool isPalindrome(std::string s) {
if (s.length() <= 1) {
return true;
}
if (s[0] == s[s.length() - 1]) {
return isPalindrome(s.substr(1, s.length() - 2));
} else {
return false;
}
}
std::string longestPalindrome(std::string s) {
std::string max_pal = "";
for (size_t i = 0; i < s.length(); ++i) {
for (size_t len = 1; len <= s.length() - i; ++len) {
std::string sub = s.substr(i,len);
if (isPalindrome(sub)) {
if (max_pal.size() < sub.size()) max_pal = sub;
}
}
}
return max_pal;
}
このアルゴリズムはO（n ^ 2）ではありませんか？非常に簡単に言えば、すべての部分文字列を生成するのにO（n ^ 2）時間かかり、それが回文であるかどうかを判断するのにO（n）時間かかります。ここで、nは最初の文字列の文字数です。
このアルゴリズムはO（n ^ 2）ではありませんか？非常に簡単に言えば、すべての部分文字列を生成するのにO（n ^ 2）時間かかり、それが回文であるかどうかを判断するのにO（n）時間かかります。
あなたが説明しているのは正確ですO(n^3)。なぜなら、各部分文字列に対して、コストのかかる操作を実行しているため、操作のO(n)総数はO(n^2 * C*n)、です。O(n^3)
ただし、説明されているコードは実際O(n^4)にisPalindrome()はO(n^2)次のとおりです。
O(n)サイズが：の部分文字列を作成しています。1 + 3 + 5 + ... + n-2これはO(n^2)合計時間です。O(n^2)回数を実行longestPalindrome()しO(n^4)ます。（これはO(n) substr()複雑さを前提としています。定義されていませんが、通常はそうです）
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加