algorithm - アナグラムアルゴの時間計算量を見つける方法

Question

序文：これは宿題の質問ではありません。Pythonでアルゴスの本を読んでいます。

アナグラムを解くための次のコードがある場合。

Public bool anagram (string a, string b) {
    return sort(a) == sort(b);
}

ソートアルゴリズムがO（n log n）であるマージソートであるとしましょう。2回実行する必要があるので、時間計算量はO（n ^ 2 log n）になりますか？

score 2 · Accepted Answer

いいえ、一定の回数実行する必要があるため、複雑さは残りO(n log n)ます。

実行する必要のある操作がもう1つあることに注意してください。つまり、文字列を比較します。ただし、それO(n)はであり、O(n + n log n)残りO(n log n)ます。

また、あなたnは「未定義」でnあることに注意してください。max(a.length, b.length)

score 1 · Accepted Answer

いいえ、になりますがO(2*[n log n])、同じですO(n log n)

それでも、長さが線形である2つのソートされた文字列を比較する必要があるため、次のようになりますO(n + n log n)。nlogn

2 に答える 2