数据结构相关笔记①

W1-W2

算法复杂度

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

T(n) = \Theta(1)

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

T(n) = \Theta(n)

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

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

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

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!

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

操作	时间复杂度	描述
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` 的现有元素将前移。

例子

操作	单向链表	双向链表	描述
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`）。

例子

例子