比較関数がO（1）でない場合、algをソートする時間の複雑さは何ですか？

Question

比較関数がO(1)の場合、効率的な並べ替え時間の複雑さはO(N*log(N))です。

比較機能がO(1)（つまりO(M)）でない場合、時間の複雑さは何ですか？

O(N*log(N*M))またはO(N*M*log(N))ですか？ ALGをソート

おかげefficentで

Answer 1

各比較にO（1）時間がかかる場合は、完了するまでにM回かかることがあります - O（M） M * N log N）。これは、MがNと共に成長し、一定ではないと仮定している。定数は大きなOh表記（O（定数）== O（1））から削除されるため、この場合の複雑さは変わりません。これはまた、ほとんどのソートアルゴリズムと同様に、O（Y）ソートアルゴリズムがO（Y）のオーダーで実行されることを前提としています。

Answer 2

たちは(N)のアイテムを持っており、各項目 のために私たちは、ソートのために結果.that O(LOG N)比較を持っている：O(N* LOG N)。 比較する場合はO(1)を指定しています。O(1*N) = O(N)

並列コンピュータアーキテクチャでは、並列ソートが可能です。 しかし、非パラメルコンピュータでは不可能ですO(1*N)