algorithm - 挿入ソートの実行時の複雑さの最も良い説明は何ですか

Question

二次式であると理解しましたが、離散数学の多肢選択式の模擬テストを受けており、4つのオプションのみがあります。

a）対数

b）線形

c）linearithmic

d）多項式

Answer 1

a）対数= O（log n）

b）線形= O（n）

c）linearithmic = O（n log n）

d）多項式= O（n ^k）

したがって、O（n ²）は多項式になります。

Answer 2

ソートされた値のリストまたはツリーに新しい値を挿入するのはO（log n）です。

まっすぐにソートされたリストで最も見やすくなります。xを挿入するとします。[n/2]で値を見つけます。これがxより大きい場合、正しい位置は左半分にあります。[n / 2]がxより小さい場合、正しい位置は右側にあります。繰り返し、毎回中央の値を確認します。各ステップは、正しい値が見つかるまでチェックする間隔のサイズを半分にし、挿入の対数時間を与えます。

ツリーへの挿入も同様です。ツリーを正しいノード位置までトラバースする必要があります。これには、lognに比例するツリーの平均深度をトラバースする必要があります。