数据结构相关笔记①

W1-W2

算法复杂度

算法复杂度描述了算法执行时间或空间随输入规模变化的增长趋势。以下是常见的算法复杂度及其表示方式：

常数 (Constant)

$T(n) = \Theta(1)$

对数 (Logarithmic)

$T(n) = \Theta(\log n)$

线性 (Linear)

$T(n) = \Theta(n)$

准线性 (Quasi-linear)

$T(n) = \Theta(n \log n)$

二次 (Quadratic)

$T(n) = \Theta(n^2)$

三次 (Cubic)

$T(n) = \Theta(n^3)$

指数 (Exponential)

$T(n) = \Theta(c^n)$

排序

$1 \quad < \quad \log n \quad < \quad \sqrt{\log n} \quad < \quad \sqrt{n} \quad < \quad n \quad < \quad n \log n \quad < \quad n \log^2 n \quad < \quad n^2 \quad < \quad n^3 \quad < \quad n^{\log n} \quad < \quad 2^n \quad < \quad n!$

抽象数据类型 (ADT)

抽象数据类型 Abstract Data Type,是一种数据类型，其特征仅由其行为（操作）定义，而不是其具体实现。例如，栈、队列、链表、树等都是抽象数据类型。

索引列表 (Index-Based List) 数组

操作	时间复杂度	描述
size()	$O(1)$	返回存储中的元素数量。
isEmpty()	$O(1)$	检查存储是否为空。
get(i)	$O(1)$	返回索引为 `i` 的元素。
set(i, e)	$O(1)$	将索引 `i` 处的元素替换为元素 `e`，并返回被替换的元素。
add(i, e)	$O(n)$	在索引 `i` 处插入元素 `e`。索引大于或等于 `i` 的现有元素将后移。
remove(i)	$O(n)$	移除并返回索引 `i` 处的元素。索引大于或等于 `i` 的现有元素将前移。

例子

Method	Returned value	List content
add(0, A)	-	[A]
add(0, B)	-	[B, A]
get(1)	A	[B, A]
set(2, C)	“error”	[B, A]
add(2, C)	-	[B, A, C]
add(4, D)	“error”	[B, A, C]
remove(1)	A	[B, C]
add(1, D)	-	[B, D, C]
add(1, E)	-	[B, E, D, C]
get(4)	“error”	[B, E, D, C]
add(4, F)	-	[B, E, D, C, F]
set(2, G)	D	[B, E, G, C, F]

位置列表 (Positional List) 单/双向链表

操作	单向链表	双向链表	描述
size()	$O(1)$	$O(1)$	返回存储中的元素数量。
isEmpty()	$O(1)$	$O(1)$	检查存储是否为空。
first(e)	$O(1)$	$O(1)$	返回第一个元素的位置（如果为空则返回 `null`）。
last(e)	$O(n)$	$O(1)$	返回最后一个元素的位置（如果为空则返回 `null`）。
removeFirst()	$O(1)$	$O(1)$	移除并返回第一个元素。
removeLast()	$O(n)$	$O(1)$	移除并返回最后一个元素。
insertBefore(p, e)	不适用	$O(1)$	在位置 `p` 之前插入元素 `e`。
insertAfter(p, e)	$O(1)$	$O(1)$	在位置 `p` 之后插入元素 `e`。
remove(p)	$O(n)$	$O(1)$	移除并返回位置 `p` 处的元素。
before(p)	不适用	$O(1)$	返回位置 `p` 的前一个元素的位置（如果 `p` 是第一个位置则返回 `null`）。
after(p)	$O(1)$	$O(1)$	返回位置 `p` 的后一个元素的位置（如果 `p` 是最后一个位置则返回 `null`）。

栈 (Stack)

操作	时间复杂度	描述
push(e)	$O(1)$	插入元素 `e`。
pop()	$O(1)$	移除并返回最后插入的元素。
top()	$O(1)$	返回最后插入的元素，但不移除。
size()	$O(1)$	返回存储中的元素数量。
isEmpty()	$O(1)$	检查存储是否为空。

例子

operation	returns	stack
push(5)	-	[5]
push(3)	-	[5, 3]
size()	2	[5, 3]
pop()	3	[5]
isEmpty()	False	[5]
pop()	5	[]
isEmpty()	True	[]
push(7)	-	[7]
push(9)	-	[7, 9]
top()	9	[7, 9]
push(4)	-	[7, 9, 4]
pop()	4	[7, 9]

队列 (Queue)

操作	时间复杂度	描述
enqueue(e)	$O(1)$	插入元素 `e` 到队列的末尾。
dequeue()	$O(1)$	移除并返回队列前端的元素。队列为空返回 nul
first()	$O(1)$	返回队列前端的元素，但不移除它。队列为空返回 null
size()	$O(1)$	返回队列中存储的元素数量。
isEmpty()	$O(1)$	检查队列是否为空。

例子

Operation	Output	Queue
enqueue(5)	-	(5)
enqueue(3)	-	(5, 3)
dequeue()	5	(3)
enqueue(7)	-	(3, 7)
dequeue()	3	(7)
first()	7	(7)
dequeue()	7	()
dequeue()	null	()
isEmpty()	true	()
enqueue(9)	-	(9)
enqueue(7)	-	(9, 7)
size()	2	(9, 7)
enqueue(3)	-	(9, 7, 3)
enqueue(5)	-	(9, 7, 3, 5)
dequeue()	9	(7, 3, 5)