Big Oの近似は正しいですか？

Question

私は2つの文字列が互いの順列であるかどうかを判断するアルゴリズムを持っています。コードはここで見つけることができます：https://jsfiddle.net/bxohcgjn/

N = String A 
M = String B 
For time complexity, i have: O(N(N logN + M logM)) 
For space complexity, I have: O(N + M) 

N logN = for sorting A 
M logM = for sorting B 

私は、ソートのためのブラウザの実装はそれを変更することを理解し、私はクイックソートを想定しています。

これについて私の思考が正しいかどうかを見たいだけです。

Answer 1

時間の複雑さについては、forループ（直線の順序）は、両方ともsortの合計で乗算してはいけません。

アルゴリズムはnのステップで構成されている場合、アルゴリズムの順序は、その注文の合計です：あなたのケースでは

O(alg) = O(step_1) + O(step_2) + ... + O(step_n) 

、n = 3（sort sおよびfor両方）：

O(is_permutation) = O(sort_A) + O(sort_B) + O(for) 
        = O(n logn) + O(m logm) + O(n) 

これらの最大値はどれですか：

O(is_permutation) = max(O(n logn), O(m logm), O(n)) 

しかし、最悪の場合（分析対象のもの）sortを適用する前に、両方の文字列のサイズが同じでなければならないことを前にテストしているため、サイズは1つのみであるため、式は

O(is_permutation) = max(O(n logn), O(n logn), O(n)) 
        = max(O(n logn), O(n)) 
        = O(n logn)