[解決済み] O(logn)とO(nlogn)の相違点

質問

ソフトウェア開発の面接を控えているのですが、O(logn)とO(nLogn)の違いの判別にいつも困っています。どなたか例を挙げて説明してくださるか、リソースを共有していただけませんか。私は示すべきコードを持っていないのです。私はO(Logn)を理解していますが、O(nlogn)を理解していません。

どのように解決するのですか？

と考えてください。 O(n*log(n)) をすることです。 log(n) 仕事 n 回"です。例えば、長さのソートされたリストの中で要素を検索する場合 n は O(log(n)) . で要素を検索すると n 異なるソートされたリスト、それぞれの長さは n は O(n*log(n)) .

を思い出してください。 O(n) が定義されています。 ある実数値nに対する相対値 . これはリストのサイズかもしれないし、コレクションに含まれるさまざまな要素の数かもしれません。したがって O(...) は、実行時間を増加させるために相互作用する何かを表します。 O(n*m) は次のように書くことができます。 O(n_1 + n_2 + ... + n_m) という同じことを表しています。 n , m 回"。

具体的な例を挙げてみましょう。 mergesort . については n の入力要素です。ソートの最後の反復では、2つの入力があり、それぞれ半分の大きさです。 n/2 そして、それぞれの半分がソートされています。私たちがしなければならないのは、それらを一緒にマージすることです。 n の演算が必要です。最後の反復では、2倍の個数(4個)のそれぞれサイズ n/4 . サイズの2つのペアそれぞれについて n/4 の場合、そのペアをマージします。 n/2 演算をペアで行う（前と同じように，ペアの各要素に1つずつ），すなわち n の操作を2つのペアで行うことができます。

ここから推測すると、マージソートの各レベルには n 操作でマージします。したがって、Big-Oの複雑さは n 倍 レベルの数 . 最後のレベルでは、マージするチャンクのサイズが n/2 . その前に、それは n/4 その前に n/8 など、すべてのサイズに 1 . を何回分割しなければならないか？ n を 2 で割ると 1 ? log(n) . そこで、次のようになります。 log(n) のレベルになります。したがって、私たちの総ランタイムが O(n (work per level) * log(n) (number of levels)) , n 仕事 log(n) 回です。