java algorithms collections
1.0.0
自定義收集初級Java開發人員角色的技術訪談數據。
在此處查看整個列表
n時間複雜性 - 輸入中的元素數量。
n在空間複雜性中 - 以表示輸入所需的位單位的輸入大小。
| 類型 | 姓名 | 解釋 | 地位 | 例子 |
|---|---|---|---|---|
O(1) | 恆定時間 | 無論輸入的大小如何 | 出色的 | 按鍵在哈希表中搜索 |
O(log n) | 對數時間 | 與輸入數據的大小增加相比，執行時間的增加非常緩慢 | 出色的 | 二進制搜索（平均） |
O(n) | 線性時間 | 執行時間與輸入數據的大小線性成正比 | 好的 | 蠻力搜索 |
O(n + k) | 組合/添加時間 | 兩個單獨輸入的複雜性 | 好的 | 計數排序 |
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 | 隊列，Deque | 不 | 不 | 不 |
| 哈希集 | 放 | 不 | 是的 | 不 |
| 樹 | 設置，排序集 | 是的 | 不 | 是的 |
| linkedhashset | 放 | 不 | 是的 | 不 |
| 哈希圖 | 地圖 | 不 | 是的 | 不 |
| LinkedHashMap | 地圖 | 不 | 是的 | 不 |
| Treemap | 地圖，排序圖 | 是的 | 不 | 是的 |
涉及排序的數據結構不允許零值。
