私はここにサイトwww.interviewcake.comからこのコードを持っています。サイトはO（n）であると言っています、そしてインタビューケーキでチームメンバーに説明を求めたところ、彼らはこれが真実であることを確認しました。コードは次のとおりです。
function reverseWords(message) {
// First we reverse all the characters in the entire message
reverseCharacters(message, 0, message.length - 1);
// This gives us the right word order
// but with each word backward
// Now we'll make the words forward again
// by reversing each word's characters
// We hold the index of the *start* of the current word
// as we look for the *end* of the current word
let currentWordStartIndex = 0;
for (let i = 0; i <= message.length; i++) {
// Found the end of the current word!
if (i === message.length || message[i] === ' ') {
// If we haven't exhausted the string our
// next word's start is one character ahead
reverseCharacters(message, currentWordStartIndex, i - 1);
currentWordStartIndex = i + 1;
}
}
}
function reverseCharacters(message, leftIndex, rightIndex) {
// Walk towards the middle, from both sides
while (leftIndex < rightIndex) {
// Swap the left char and right char
const temp = message[leftIndex];
message[leftIndex] = message[rightIndex];
message[rightIndex] = temp;
leftIndex++;
rightIndex--;
}
}インタビューケーキのチームメンバーがこれを言ったという説明：
*はい、O（n ^ 2）のように見えるネストされたループがあります。
しかし、問題の過程で、各内部ループでO（n）文字を反転していないことがわかります...各文字を正確に2回だけ反転します。したがって、総コストはO（n）になります。
これはトリッキーなものです。なぜなら、各呼び出しを単独で行うのではなく、アルゴリズム全体でreverseCharactersへのすべての呼び出しのコストを調べる必要があるからです。*
ただし、内側のループで各文字をループしているため、まだ混乱しています。文字列が大きくなるほど、呼び出しの実行に時間がかかります。
これを別のチャネルに開いて、これについてさらに洞察を得ることができるかどうか、そしてなぜO（n）^ 2ではなくO（n）であるのかを確認したかったのです。
完全に明確にするために、reverseWords上記のコードの関数がO（n）^ 2ではなくO（n）である理由について説明したいと思います。
そのコードで私が言えることから、外側のループの仕事は各単語の終わりを探すことです。1つが見つかると（そしてそのときだけ）、reverseCharacters()その単語の文字を逆にするために呼び出されます。したがって、2つのタスクの大きなOは、乗算される（O（n）* O）のではなく、加算されます（O（n）+ O（n）= O（2n）、これは依然としてO（n）と見なされます）。 （n）= O（n ^ 2））は、ネストされたループで通常行われると予想されるとおりです。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加