java algorithms collections
1.0.0
ジュニアJava開発者の役割のための技術インタビューのためのデータのカスタムコレクション。
ここでリスト全体を参照してください
n時間の複雑さ - 入力の要素の数。
n空間の複雑さのn - 入力を表すために必要なビット単位の入力サイズ。
| タイプ | 名前 | 説明 | 状態 | 例 |
|---|---|---|---|---|
O(1) | 一定の時間 | アルゴリズムは、入力のサイズに関係なく、毎回同じ回数で実行されます | 素晴らしい | キーによるハッシュテーブルで検索します |
O(log n) | 対数時間 | 実行時間は、入力データのサイズの増加に比べて非常にゆっくりと増加します | 素晴らしい | バイナリ検索（平均） |
O(n) | 線形時間 | 実行時間は、入力データのサイズに直線的に比例します | 良い | ブルートフォース検索 |
O(n + k) | 組み合わせ/添加時間 | 2つの個別の入力の複雑さを組み合わせました | 良い | カウントソート |
O(n log n) | 準線形時間 | 入力サイズが増えると、対数成長のために問題を解決するために必要な部門の数がゆっくりと増加します | 悪い | ソートをマージし、ヒープソート |
O(n^2) | 二次時間 | 各要素のネストされた反復または比較が含まれます | 最悪 | 選択ソート |
O(2^n) | 指数時間 | 入力のすべての可能な組み合わせの徹底的な検索または列挙、実行時間は指数関数的に増加します | 最悪 | TSP（動的プログラミング） |
O(n!) | 要因時間 | 入力のすべての可能な組み合わせの徹底的な検索または列挙、実行時間は要因的に増加します | 最悪 | TSP（ブルートフォース） |
| タイプ | 名前 | 説明 | 状態 | 例 |
|---|---|---|---|---|
O(1) | 一定のスペース | アルゴリズムには、入力サイズに関係なく、固定量の追加メモリが必要です | 素晴らしい | ヒープソート |
O(log n) | 対数空間 | 入力データのサイズの増加に比べて、スペースの使用量はゆっくりと増加します | 素晴らしい | クイックソート |
O(n) | 線形空間 | スペース使用量は、入力サイズで直線的にスケーリングします | 良い | ソートをマージします |
O(n + k) | 組み合わせ/添加剤スペース | nとkの合計で空間使用量が直線的にスケーリングします | 悪い | RADIXソート |
| 学期 | 意味 | 例 |
|---|---|---|
| 抽象データ型（ADT） | 特定の実装の詳細ではなく、その動作と操作に焦点を当てたデータ型の高レベルの説明を表します | スタック、キュー、辞書、シーケンス、セット |
| データ構造 | 特定のデータ型を実装し、データを特定の方法で整理および保存するための手法または戦略 | 配列、リンクリスト、ハッシュテーブル、ツリー（バイナリ検索ツリー、ヒープ、赤/黒い木 |
| タイプ | 複製要素 | 要素の順序 | 特定の順序で追加/削除する必要があります |
|---|---|---|---|
| リスト | 許可された | インデックスによって | いいえ |
| 地図 | 値に許可されています | JavaはキーのHashCode（）を使用して順序を決定します。 | いいえ |
| 列 | 許可された | 定義された順序で取得 | はい |
| セット | 禁止 | ツリーセットでのみ | はい |
| タイプ | インタフェース | ソート？ | hashCode()を呼び出しますか？ | compareTo()を呼び出しますか？ |
|---|---|---|---|---|
| arrayList | リスト | いいえ | いいえ | いいえ |
| LinkedList | リスト、deque | いいえ | いいえ | いいえ |
| arraydeque | キュー、デク | いいえ | いいえ | いいえ |
| ハッシュセット | セット | いいえ | はい | いいえ |
| ツリーセット | セット、ソートセット | はい | いいえ | はい |
| LinkedHashset | セット | いいえ | はい | いいえ |
| ハッシュマップ | 地図 | いいえ | はい | いいえ |
| LinkedHashmap | 地図 | いいえ | はい | いいえ |
| Treemap | マップ、sortedmap | はい | いいえ | はい |
ソートを含むデータ構造は、ヌル値を許可しません。
