# 算法与复杂度

算法 (Algorithm)「アルゴリズム」，是指解决问题的一系列步骤或规则
通常来说，算法的讲解会使用 伪代码 (Pseudocode)「擬似コード」，而非特定的编程语言

例如，Euclid 辗转相除法的算法可以用伪代码表示如下

int Euclid(int m,int n) {//return gcd(m,n)
    repeat
        r = m mod n
        if r == 0 return n
        m = n
        n = r
}

---

复杂度 (Complexity)「計算量」，是指算法在执行过程中所需要的资源量
一般来说是指当输入的数据规模为 $n$ 时，算法所需要的时间量或者空间量的上界
并且作为 $n \to \infty$ 时的渐近行为，使用 Landau 记号表示，例如 $O(n^2)$，$O(n \log n)$，$O(2^n)$ 等等

例如我们考虑一个搜索例子：给定一个长度为 $n$ 的已经排序的数组 $A$ 和一个目标值 $x$，判断 $x$ 是否在 $A$ 中
简单的线性搜索方式是从第一个开始一个个找过去，直到找到 $x$ 或者搜索完整个数组。因此时间复杂度为 $O(n)$
然而如果我们使用二分搜索方式，先比较 $x$ 与数组中间位置的元素 $A[\lfloor n/2 \rfloor]$ 的大小关系，如果 $x < A[\lfloor n/2 \rfloor]$，则继续在前半部分搜索；如果 $x > A[\lfloor n/2 \rfloor]$，则继续在后半部分搜索；如果 $x = A[\lfloor n/2 \rfloor]$，则搜索成功。
这样一来，最差的情况下搜索的次数为 $\log_2 n$，因此时间复杂度为 $O(\log n)$，比线性搜索的 $O(n)$ 要好得多

---

数据结构 (Data Structure)「データ構造」，是指在计算机中组织和存储数据的方式
本节介绍一系列常见的数据结构

# 基本数据结构

数组 (Array)「配列」，是指在内存中连续存储的一系列元素。通常是静态固定的，读取效率高但是插入和删除效率低
例如如果想要在中间插入一个值，就必须让后面的元素都往后移动一位（因为是连续空间），因此时间复杂度为 $O(n)$；如果想要在中间删除一个值，也必须让后面的元素都往前移动一位，因此时间复杂度也是 $O(n)$
但是读取只需要找到那个坐标，所以读取效率为 $O(1)$

---

链表 (Linked List)「リスト」，内存中的分散空间。每个数据单元（节点）除了存储数据本身，还必须额外存储一个指向下一个节点内存地址的 “指针”。因此空间是动态的，插入和删除效率高但是读取效率低
例如想要插入一个值，只需要修改前一个节点的指针指向新节点，新节点的指针指向后一个节点，因此时间复杂度为 $O(1)$；想要删除一个值，只需要修改前一个节点的指针指向后一个节点，因此时间复杂度也是 $O(1)$
然而读取一个值就意味着必须从头节点开始一个个往下找，直到找到那个值或者找到链表的末尾，因此时间复杂度为 $O(n)$

---

栈 (Stack)「スタック」，是指一种后进先出（LIFO）的数据结构。只能在一端进行插入 (push) 和删除 (pop) 操作
可以想象在一个木棍上一层一层地堆积中空圆盘，我们每次只能在最上面插入一个圆盘或者从最上面删除一个圆盘（这个小游戏应该比较广为人知）

---

队列 (Queue)「待ち行列」，是指一种先进先出（FIFO）的数据结构。只能在一端进行插入操作，在另一端进行删除操作

• 插入被称为 入队 (Enqueue)「エンキュー」
• 删除被称为 出队 (Dequeue)「デキュー」

如果利用数组来实现队列，那么每次出队的操作都会导致后面的元素往前移动一位，因此时间复杂度为 $O(n)$，效率较低
因此，可以考虑将队列实现为一个循环数组，或者使用链表来实现，这样就可以在 $O(1)$ 的时间复杂度内完成入队和出队操作

---

树 (Tree)「木」，是指一种分层的数据结构，由 节点 (Node)「ノード」 组成，其中每个节点可以有零个或多个子节点，并且没有父节点的节点被称为根节点
不具有子节点的节点被称为 叶 (Leaf)「葉」，具有相同父节点的节点被称为兄弟节点

---

图 (Graph)「グラフ」，是指由一组顶点（节点）和连接这些顶点的边组成的数据结构
可以使用邻接矩阵或者邻接表来表示图

# 优先队列

优先队列 (Priority Queue)「優先度付き待ち行列」，是指一种特殊的队列，其中每个元素都有一个与之相关的优先级。元素按照优先级顺序进行处理，而不是按照它们进入队列的顺序