35

配列、リンクされたリスト、ハッシュ テーブルなどを含む最も一般的なデータ構造に対する操作の Big O 表記の概要はありません。

4

6 に答える 6

78

このトピックに関する情報は、ウィキペディアの検索データ構造で入手できるようになりました。

+----------------------+----------+------------+----------+--------------+
|                      |  Insert  |   Delete   |  Search  | Space Usage  |
+----------------------+----------+------------+----------+--------------+
| Unsorted array       | O(1)     | O(1)       | O(n)     | O(n)         |
| Value-indexed array  | O(1)     | O(1)       | O(1)     | O(n)         |
| Sorted array         | O(n)     | O(n)       | O(log n) | O(n)         |
| Unsorted linked list | O(1)*    | O(1)*      | O(n)     | O(n)         |
| Sorted linked list   | O(n)*    | O(1)*      | O(n)     | O(n)         |
| Balanced binary tree | O(log n) | O(log n)   | O(log n) | O(n)         |
| Heap                 | O(log n) | O(log n)** | O(n)     | O(n)         |
| Hash table           | O(1)     | O(1)       | O(1)     | O(n)         |
+----------------------+----------+------------+----------+--------------+

 * The cost to add or delete an element into a known location in the list 
   (i.e. if you have an iterator to the location) is O(1). If you don't 
   know the location, then you need to traverse the list to the location
   of deletion/insertion, which takes O(n) time. 

** The deletion cost is O(log n) for the minimum or maximum, O(n) for an
   arbitrary element.
于 2013-07-01T17:12:59.870 に答える
16

リンクされたリストの時間の複雑さから始めると思います。

索引付け---->O(n)
最後に挿入/削除---->O(1) または O(n)
途中で挿入/削除--->O(1) イテレータあり O(n) なし

最後に挿入するための時間の複雑さは、最後のノードの場所があるかどうかによって異なります。そうでない場合は、リンクされたリストを検索する必要があり、時間の複雑さは O(1) になります。 （n）。

于 2008-09-23T18:37:53.637 に答える
4

赤黒木:

  • 挿入 - O(log n)
  • 取得 - O(log n)
  • 削除 - O(log n)
于 2008-09-23T21:04:18.777 に答える
4

独自のデータ構造 (C のリンク リストなど) を作成する場合を除き、選択した言語/フレームワークでのデータ構造の実装に大きく依存する可能性があることに注意してください。例として、 Ridiculous Fish で Apple の CFArrayのベンチマークを見てみましょう。この場合、Apple の CoreFoundation フレームワークの CFArray であるデータ型は、配列内に実際に含まれるオブジェクトの数に応じてデータ構造を実際に変更し、約 30,000 オブジェクトで線形時間から一定時間に変更します。

これは、実際にはオブジェクト指向プログラミングの優れた点の 1 つです。それがどのように機能するかを知る必要はなく、単に機能するだけであり、「どのように機能するか」は要件に応じて変更できます。

于 2008-09-24T22:22:09.890 に答える
1

ハッシュテーブルの償却 Big-O:

  • 挿入 - O(1)
  • 取得 - O(1)
  • 削除 - O(1)

ハッシュアルゴリズムには一定の係数があり、償却は実際に測定されたパフォーマンスが劇的に異なる可能性があることを意味することに注意してください。

于 2008-09-23T21:01:11.013 に答える