BigO時間性比較.xlsx

	A	B	C	D
1	operations	Array	Singly Linked List	Doubly Linked List
2	任意位置插入	O(1) 有index	O(n) Node組成，沒有index，假設要palindrome，鏈表需要遍歷每一個值	O(n) Node組成，沒有index，假設要palindrome，鏈表需要遍歷每一個值
3	head 插入/刪除	O(n) 長度固定，需要移動元素來為新元素騰出空間	O(1) 只需修改頭指針	O(1) 只要修改頭指針和第一個節點的前驅指針
4	tail 插入/刪除	O(1) 直接在tail增加或刪除	O(1)/O(n) 如果不知道tail	O(1)/O(n) 如果不知道tail
5	任意位置插入/刪除	O(n) 長度固定，需要移動元素來為新元素騰出空間，刪除元素時需要將後面的元素往前移動	O(n)	O(n)
6	內存	不需要額外的內存	需要額外的內存來指向下一個元素的指針	需要額外的內存來指向下一個元素的指針
7
8
9
10	operations	Stack
11	push (in)	O(1)
12	pop (out)	O(1)
13	Peek (查看頂端)	O(1)
14	IsEmpty (是否為空)	O(1)
15	內存	使用陣列或鏈表等基本的數據結構，不需要額外的動態分配內存
16
17
18	operations	Queue
19	enqueue (in)	O(1)
20	dequeue (out)	O(1)
21	peek (查看頂端)	O(1)
22	IsEmpty (是否為空)	O(1)
23	內存	使用陣列或鏈表等基本的數據結構，不需要額外的動態分配內存
24
25
26	operations	Regression
27	push (in)	O(1)
28	pop (out)	O(1)
29	peek (查看頂端)	O(1)
30	IsEmpty (是否為空)	O(1)
31	內存	使用陣列或鏈表等基本的數據結構，不需要額外的動態分配內存
32
33
34
35	operations	二元樹（Binary Tree）	二元搜尋樹(Binary Search Tree)	滿二元樹（Full Binary Tree）
36	insert	O(log n)、O(n) 一條鏈表	O(log n)、O(n) 一條鏈表	O(log n)
37	search	O(log n)、O(n) 一條鏈表	O(log n)、O(n) 一條鏈表	O(log n)
38	delete	O(log n)、O(n) 一條鏈表	O(log n)、O(n) 一條鏈表	O(log n)
39	內存	沒有特定的限制，可以形成任何形狀的樹	在最壞情況下，可能退化成一條鏈表，內存使用量較高自平衡搜尋樹（如 AVL 樹、紅黑樹），內存使用量較高，來保持平衡	始終保持平衡，內存使用量較高，因為樹的高度是固定的
40
41
42
43		n=node數量, e=edge數量
44	operations	graph_adjacency matrix	graph_adjacency list
45	add node	O(n^2) 假設原本是33，增加一個變44	O(1)
46	add edge	O(1)	O(1)
47	delete node	O(1)	O(2n) 兩端的點都要遍歷一次
48	delete edge	O(n^2) 假設原本是44，刪除一個變33	O(n+e)
49	內存	需要較多內存，因為它存儲所有節點和邊的信息，能快速查找點和點之間的關係	需要較少的內存，只存儲實際存在的邊，當有很多邊是0時，適合使用，例如ig追蹤者的關聯
50
51
52
53	operations	Tree Traversal	Graph Traversal	內存
54	Breadth First Search, BFS 廣度優先搜尋 (queue 先進先出)	O(n)	O(n+m)，其中 n 是節點數，m 是邊數最壞情況下，要訪問所有節點和邊	BFS通常使用一個佇列（Queue）來保存待處理的節點佇列的大小通常不會超過節點數 BFS在內存使用上較 DFS 穩定，最壞情況下的內存使用通常更容易預測
55	Depth First Search, DFS 深度優先搜尋 (stack 先進後出，後進先出)	O(n)	O(n+m)，其中 n 是節點數，m 是邊數最壞情況下，要訪問所有節點和邊	DFS 在內存使用上取決於堆疊的深度，而堆疊的深度取決於樹的高度或圖的最深路徑的深度 O(h) h 是樹的高度或圖的最深路徑的深度
56
57
58
59	operations
60	Bubble Sort 氣泡排序	O(n^2)、O(n)列表已經排序好時
61	Bubble Sort 改進的氣泡排序	在每一輪冒泡中，記錄最後一次交換的位置，下一輪只需要比較到這個位置即可，減少無效的比較
62	Cocktail Shaker Sort 鸽巢排序	Bubble Sort 的變種，從左到右和從右到左都進行冒泡，可以稍微提高效率
63	Selection Sort 選擇排序	O(n)（當列表已經排序好時）
64	Insertion Sort 插入排序	O(n^2)、O(n)列表已經排序好時
65	Binary Insertion Sort 二分插入排序	使用二分搜索來找到插入位置，減少比較次數
66	Shell Sort 希爾排序
67	Merge Sort 歸併排序	O(n log n)
68	QuickSort 快速排序	O(n^2) 為了避免最壞情況發生，會使用隨機選擇基準元素，或使用三數取中法，來提高算法的性能、O(n log n)
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100