【Day 18】Complexity & Graphs

接下来我们要针对复杂度做介绍，首先要说的就是高手们常常说的「Big O」! 但是到底什麽是 big O notation 呢？

Big O

在电脑科学中，big O 可以帮助我们分析演算法效率：
设, ，且存在一正数 C 与一数 N 使得 for all ，则 。
也就是说，当 n 够大时，g(n) 的影响力会比 f(n) 大。

举个例子：

而

可以发现，在计算 Big O 时，我们是忽略掉常数项不计的。

Graphs / Networks

由 nodes 与 edges 交织而成。
nodes 可以理解为一个点的位置，而 edges 则是通往别的点的路径，与两点中间若有 edge，即称这两个点为 neighbors，而一个 node 有多少 neighbor 就代表他有多少 degree。

Edges有两个种类：

1. Directed edges：记为 (u, v)。
2. Undirected edges：记为 [u, v]。
   以上图为例，因上图相接的 edge 是没有方向性的，像是 [1, 2] = [2, 1]，因此上图为一 undirected graph。

Path
path 又称为 route，以上图为例：若我们想要从 node1 走到 node6，我们有好几种方式：
(1, 5, 4, 6)、(1, 2 ,3 ,4, 6)、(1, 3, 4, 6)。

Cycle
若ㄧ路径起点与终点相同，则我们称此为一个 cycle。
一个不含 cycle 的path称作「simple path」。
一个不含 cycle的graph称作「acyclic graph」。

Weights
我们可以在每条 edge 上添加上数字，代表 distance、cost 等等。
例如：

(1, 2, 3, 4) 的距离即为13。

Adjacency matrix & Adjacency list

由於在程序码不能读取我们的图，但是可以用adjacency matrix来储存graph的资讯，不过有的时候，adjacency matrix会太占空间，因此也很常用另一种方式：adjacency list。

如果我们想要存谁是neighbors，只要是 neighbors 就在 matrix 中以 1 表示。

Graph algorithms

一个 graph 可以表达很多资讯，例如我们想找到各点的最短路径的话，可以将所有最短路径画成一个树状图如下图。

而依照此树状图，有两种演算法可以帮助我们做搜寻 nodes，分别为：

1. Breadth-first search (BFS) 广度优先
2. Depth-first search (DFS) 深度优先

这边有一篇文章我认为讲得十分清楚，附上网址给大家做参考：深度优先搜寻(DFS)和广度优先搜寻(BFS)演算法，实用的节点搜寻法