インデックスX(0≦X < 2N)の要素がX xor 3(つまり、Xの2つの最下位ビットが反転されている)の2^Nのサイズを持つ整数の配列を考えてみましょう。この配列の挿入ソートの実行時間はどれくらいですか?2^N配列の挿入ソートの時間の複雑さ?
-1
A
答えて
1
リストがどのように見えるかの構造を調べ、N = 3の場合
{3、2、1、0}
:N = 2の場合
を
{ 3、2、1、0、7、6、5、4}
挿入ソートの場合、1から現在のインデックスまでのリストがソートされているので不変であるため、それぞれステップはcを配置することですそれ以前のソートされた要素の中の正しい場所です。最悪の場合、現在の値を挿入する前に、以前のすべてのインデックスをトラバースする必要があります(リストが逆ソート順である場合を考えてください)。しかし、上記の構造から明らかなように、各値がインデックス^ 3に等しいというプロパティを持つリストの場合、指定されたインデックスから移動しなければならないリストの中で最も遠いものは3です。したがって、あなたはO(n)を挿入段階で一定の要素に作用させなければならない可能性があります。しかし、リストの各要素を調べるためにはまだO(n)の作業をしなければなりません。したがって、この特定のケースでは、挿入ソートの実行時間は入力のサイズに対して線形ですが、最悪の場合は2次です。
関連する問題
- 1. 挿入の時間複雑度ソート基準。 Based Linked-List?
- 2. 時間複雑ソート
- 3. ループ内でのRBツリーの挿入時間の複雑さ
- 4. 入力のエンコーディング(時間の複雑さ)
- 5. ソート時の複雑
- 6. 未分類配列のバイナリ検索の時間の複雑さ
- 7. なぜ配列挿入の時間複雑さはO(n)で、O(n + 1)ではないのですか?
- 8. 二重リンクリストを使用した挿入ソートの複雑さ?
- 9. 配列リストを反復する時間の複雑さ
- 10. 文字列の配列をソートするための最適なアルゴリズムと時間の複雑さ?
- 11. 時間の複雑さと
- 12. ソートを計算する時間の複雑さ
- 13. 時間の複雑さと空間の複雑さ、空間の複雑さの計算方法
- 14. 複雑::挿入()
- 15. 複数ソートされた配列とその複雑さの検索
- 16. このアプローチの時間の複雑さ
- 17. 空間複雑性:リンクリストノード(ヘッド)の配列
- 18. 配列の時間の複雑さから最大のJavaを見つける
- 19. 時間の複雑さ(入れ子にされたループ)
- 20. fun()の時間の複雑さ?
- 21. ファイル修正の時間の複雑さ?
- 22. 時間複雑
- 23. 時間複雑
- 24. 時間複雑
- 25. 行列の鎖の乗算の時間の複雑さ
- 26. Pythonでの文字列連結の時間の複雑さ
- 27. マスターメソッドを使用してT(n)= 9T(n/3)+ 2n^2 + n/3の時間複雑さを解く方法は?
- 28. 時間の複雑さは、Python
- 29. 計算時間の複雑さ
- 30. 時間の複雑さ(Java、Quicksort)
なぜこの質問に誰かが投票したのか分かりません。私はそれが解決策を見つけることができなかったので、私は私がここでコミュニティに尋ねるべきだと思ったサーフでした。 – shubhamrock828
これは検索が非常に簡単であるため、あなたはおそらくダウン投票されました。グーグル「挿入ソート時間の複雑さ」は、第2の結果としてhttp://bigocheatsheet.com/を与えました。 – Carcigenicate