Intro

Complexity 可以了解程序的运作效率

graph 可以把复杂的问题抽象化，或是可以让我们比较好理解像是 complexity 的东西。

• Issues
  • Complexity
  • The "big O" notation
  • Terminology of graphs
  • Graph algorithms

Complexity

我们在写 algorithm 的时候，可能可以使用不同的方法达到同样的效果。

但是不同的方法，就会有不同的效率，用来比较的基准，就是计算他们的 Complexity (复杂度)。

Complexity 主要可以分为两种

1. Space complexity : 花越少的空间(memory)越好

   Ex:

   Given a matrix A of m x n integer, find the row whose row sum is the largest.

   两种 algorithm:

   1. For each row, find the sum. Store the m row sums, scan through them, and find the target row.

      因为要把全部的row sum存起来，空间会使用的比较多。

      const int MAX_COL_CNT = 3;
      const int MAX_ROW_CNT = 4;
      
      //这个二维阵列最多就是 3 x 4
      
      int maxRowSum(int A[][MAX_COL_CNT], int m, int n) 
      {
      	// calculate row sum
      	int rowSum[MAX_ROW_CNT] = {0}; // for storing rowSum
      	for (int i = 0; i < m; ++i)
      	{
      		int aRowSum = 0;
      		for (int j = 0; j < n; ++j)
      			aRowSum += A[i][j];
      		rowSum[i] = aRowSum;
      	}
      	// find the row with the max row sum
      	int maxRowSumValue = rowSum[0];
      	int maxRowSumNumber = 1;
      	for (int i = 0; i < m; ++i)
      	{
      		if(rowSum[i] > maxRowSumValue)
      		{
      			maxRowSumValue = rowSum[i];
      			maxRowSumNumber = i + 1;
      		}
      	}
      	return maxRowSumNumber;
      }
      

      因为要把全部的 row sum 存起来，空间会使用的比较多。

   2. For each row, find the sum and compare it with the currently largest row sum. Update the currently largest row sum if it is larger.

      int maxRowSum(int A[][MAX_COL_CNT], int m, int n)
      {
      	int maxRowSumValue = 0;
      	int maxRowNumber = 0;
      	for (int i = 0; i < m; ++i)
      	{
      		int aRowSum = 0;
      		for (int j = 0; j < n; ++j)
      			aRowSum += A[i][j];
      
      		if (aRowSum > maxRowSumValue)
      		{
      			maxRowSumValue = aRowSum;
      			maxRowNumber = i + 1;
      		}
      	}
      
      	return maxRowSumValue;
      }
      

      只需要存取现在的 row sum，还有原本纪录着最大值，所以空间可能会使用的比较少。

   我们来比较一下两个演算法使用的空间大小:

   Algorithm 1: 宣告1个 array / 3 个 integer

   Algorithm 2: 宣告了 3 个 integer

   因此 algorithm 2 会有比较低的 lower complexity

   通常需要注意 space complexity 的程序会运行的电脑，可能存在於那种微型的装置，像是智能眼镜、冷气、或是灯等等家具上。因此在电脑领域我们通常不会太注意 space complexity 而是 time complexity。

2. Time complexity : 花越少时间越好

   • 大部分的时候，complexity 几乎等於 time complexity。

   • Time complexity 主要是在数 basic operation 的数量，而 basic operation 有:

     declaration, assignment , arithmetic, comparisons等等。

   Ex:

   就拿上面的 algorithm 1 作为例子:

   int rowSum[MAX_ROW_CNT] = {0};  //(1)
   	for (int i = 0; i < m; ++i) //(2)
   	{
   		int aRowSum = 0; //(3)
   		for (int j = 0; j < n; ++j) //(4)
   			aRowSum += A[i][j]; //()
   		rowSum[i] = aRowSum; //(6)
   	}
   
   //the remaining are skipped.
   

f(n)≥0,g(n)≥0
每一项的细算会呈现在下表:
【Algorithm1 的 operation count】

因此整体来说，我们会得到 5mn + 10m + 2 个 basic operation

但是 ! 这样仔细地计算是不是太麻烦了?

• 如果 n 足够的大，我们其实可以忽略 10m + 2 这两项， 就可以粗估成 5mn 这样子
• 因此我们可以说明 这个式子的 bottleneck (瓶颈) 就是在第一个 part → 也就是 5mn
• 而我们甚至可以把 5mn 的常数，5 省略。
• 因此，我们只需要注意当 instance size (m或是n) 变到很大的时候，产生的 bottleneck 会是谁 (只需要注意这一项就好了)。 → 所以我们根本可以只知道 他的 basic operation 最大项是 mn 就行了。

所以我们来看 algorithm 2:

 int maxRowSum(int A[][MAX_COL_CNT], int m, int n)
 {
 	int maxRowSumValue = 0;
 	int maxRowNumber = 0;
 	**for (int i = 0; i < m; ++i)**
 	{
 		int aRowSum = 0;
 		**for (int j = 0; j < n; ++j)**
 			aRowSum += A[i][j];

 		if (aRowSum > maxRowSumValue)
 		{
 			maxRowSumValue = aRowSum;
 			maxRowNumber = i + 1;
 		}
 	}

 	return maxRowSumValue;
 }

由这两行可以知道，我们可以粗估他的 basic operation 就也是

因此也可以说，这两个 algorithm 粗估的 complexity 其实一样。

The "big O" notation

简而言之， The "big O" notation 这个概念，是为了要拿来估计 complexity 的。

以数学的角度而言，the big O 的定义是:

时满足

而 的意思就是

感觉很困难，但就可以想像 f(n) 还有 g(n)是两个函数，画成图会长这样:

当 n 够大的时候， 一定可以找到某一个常数 c 乘上 g(n) 会恒大於 f(n)。

BTW，这个 O()，可以把它想像成一个函数(或者它就是，原谅我数学不好)

就像是这样，而那个 O(g(n)) 就是 c * g(n)。

如果还是听不太懂，没关系，我们直接上例子:

Ex1:

Let

因此可以找到任意多对 (c, n) 满足

Ex2:

Let

其实仔细看这个例子，可以发现 f(n) 中，因为 5n中如果 n 越大时，对於整个函式的质影响比较大，所以我们可以说 n 就是 f(n) 的 bottleneck。

简而言之，O() 的概念，就是要帮我们过滤掉不重要的资讯，忽略掉过小的质，让我们可以用最後的资讯来比较每一个 algorithm 的 basic operation，最终目的也就是要比较不同 algorithm 的Complexity。

Growth of functions:

不同的函数会有不同的成长速度，就像我上面举的那张图一样，g(n) 在最後会比 f(n)跑的还要快。

而这种情况就会说 g(n) dominate f(n)，g(n)就被称为 the upper bound。

在这张图里面可以看到，在 n^2以前的函数，大部分都增长得比较慢；但是到了2^n、n! ，他们增长的速度大幅上升。

所以在 n^2以前的函数 就会被称为 多项式复杂度 (相对比较好)

而在n^2以後的函数 就会被称为 指数型复杂度 (相对不好)

Implemental Ex1:

像是上面的 algorithm2，我们可以说他的 complexity 是 O(mn) (mn + 比它成长慢的项)

• 执行时间 会跟 阵列的 行与列成正比
• 因此在执行上，阵列是可以有数以百万计的 element的(可正常运行)

Implemental Ex2:

取比 n 小的所有质数:

// Algorithm1
#include<iostream>
using namespace std;
bool isPrime(int x);
int main()
{
	int n = 0;
	cin >> n;
	for (int i = 2; i <= n; i++)
	{
		if (isPrime(i) == true)
			cout << i << " ";
	}
	return 0;
}

// Function
bool isPrime(int x)
{
	for (int i = 2; i < x; i++)
	{
		if (x % i ==0)
			return false;
	}
	return true;
}

我们可以先看 int main()中，只有一个 for loop

可以确定她的复杂度是 n (跑 n 次)

我们再来看 isPrime():

bool isPrime(int x)
{
	for (int i = 2; i < x; i++)
	{
		if (x % i ==0)
			return false;
	}
	return true;
}

可以知道这个演算法的复杂度会取决於 isPrime()

而 isPrime() 的 operation 与 x 的大小有关系，

例如 x = 18 的时候，跑到 2就结束

但是 x = 17 的时候，他就会跑到 17 才结束。

这时候该怎麽办??

但是前辈们告诉我们没关系，如果遇到这种情况，

我们就取 Waste-case time complexity 也就是在最倒楣的时候，会发生甚麽事。

最糟的情况(就是 x = prime) → {等於说 isPrime() 从 2...判断到...(x-1)} 也就是判断 x-2 次

因此 O(x-2) 就是 O(x) (本质上没有差) ，而且因为有 for loop ， 所以我们可以知道这个演算法的the most naive complexity是 O(2 + 3 + .... + n) 也就是 O(n^2)

Implemental Ex3:

这次我们用更好一点的演算法

bool isPrime(int x)
{
	for (int i = 2; i * i <= x; i++)
	{
		if (x % i ==0)
			return false;
	}
	return true;
}

就是改了比较的值。所以如果只看 isPrime() 的复杂度，就会是 (也就是大概要跑 次)

那如果是整个演算法，就是

因此，这个演算法的复杂度就会是 ，所以理论上 Ex3 会比 Ex2 来的好。

Implemental Ex4:

更好的演算法:

Given a Boolean array A of length n
Initialize all elements in A to be true // asuming prime
for i form 2 to n
	if A_i is true
		print i
		for j from 1 to (n/i) // eliminating composite numbers 把倍数画掉
			Set A[ixj] to false

在 outer loop 里面会有 O(n) iterations，第 i 个 iteration 中，inner loop 会有 O(n/i) 个 iteration。

因此可以粗估复杂度会是

→ good!

Remarks

分析一个演算法的Complexity → important!!!

• 我们注意的是: 当 input size 时，operation 的程度

The "Big O" notation:

• 省略繁琐的细节，只关注 bottleneck
• 只关注 worse-case
• 不只有 big O 的测量方式，还有其他的 (small o, theta, big omega, small omega...)

Terminology of graphs

Graph 又会被称为 networks，像是这张图:

每一个点称为 node (可以想成地点)， 点与点之间称为 edge (可以想成道路)。

这张图就有 7 个 nodes，9 个 edges。

而两个相邻(ad)的 node 会被称为 neighbor。 像是 5 号 就会有 4 个 neighbors。

一个 node 的 degree，就是 neighbors 的数量。 (有时候两个点之间会有不只一个edge，这时候就要看 edge 是几个来判断)

Edge 分成两种:

例如今天有一个 edge 连接 u & v

• directed:

  只能从 u 走到 v ，或是从 v 走到 u

  写法会写成: (u, v)

• undirected

  无论是从 u → v 或是 v → u，龙欸赛。

  写法会写成: [u, v]

拿上面的图里举例:

可以写成 [1, 2]，或是 [2, 1]

但 [2, 3] 不存在，就不能写成 [2, 3]

Path (Route):

如果今天图变成这样，一整段路(同一颜色的)，就会被称做一段 path。

from s to t，

我们就会写成 (6, 5, 4, 1) 还有 (6, 5, 3, 1) 每一个号码的顺序是不能错的。

Cycle

那如果今天有一个 path 可以绕成一个圈，这样就会被称为一个 cycle。

像上面的会被称为 cycle (1, 4, 5, 3)。

但是中间如果有经过重复的点，就会不会被称为 simple cycle

Weight

那如果 edge 上面是有值(距离)的话，这个图就会被称为 weighted graph。

而那些值，就是 weights。

像是 distance (6, 5, 1) 就会是 17 + 6 = 23。

Storing a graph in an adjacency matrix:

要怎麽把图储存到程序里面?

有两种储存方式:

• adjacency matrices

  若 graph 上有 n 个点，我们会先做 n * n 的 array A。

  如果是 unweighted graph，则把 A 做成 Boolean array。

  • 使 ，如果 edge (i, j) * 1 存在。(如果有 n 条就 = n)
  • 使(自己到自己)

  如果是 weighted graph，则把 A 做成 Integer / float / double array。

  • 使 = weight for edge (i, j)
  • 如果两个 node 中不存在 edge，则用 (-1) 或是 (∞)等等来表示

  例如上面的 graph(第一张) 就可以写成:

  

  那如果是 weighted 的那一张，就可以写成:

  

优点: 简单、直观

缺点: 使用空间的方式太没效率，其实只需要纪录一些 edge 就好 → 因此大家就会使用 adjacency lists

• adjacency lists

纪录自己的 neighbor (或是weight 记起来)

像是:

Graph algorithms

Graph 可以拿来表示很多议题，像是电力分布、社交分布等，也因此可能会衍伸出许多 problem。

• 像是计算 两点内 最短的 path (电力网种找到最短的距离)
• 像是 找到一个 node 具有最大的 degree
• 像是 是否有 cycle 的产生，有几个 (例如 social network 中的人互相认识)

因此为了解决这些问题的 algorithm，就会被称为 graph algorithm。

implemental Ex1:

Maximum degree:

• Given : a adjacency matrix for an unweighted graph
• Target: To find the node with the maximum degree (number of neighbors)
• Method:
  • for each row, find the number of 1s
  • compare all number of 1s in every row → find the largest

implemental Ex1:

Minimum number of edges:

• Given: an undirected unweighted graph G = (V, E) & s (stand for a node)

• (V = set of nodes; E = set of edges; s = a node)

• Target: 寻找从 s 出发， 走到其他点所需要花得最少步数。

• 像上面这个例子，就可以把它画成另一种 spanning tree (扩张树)。

  

• Method: breadth-first search(BFS)

  • 把 s 标成 0 ，剩下都标成 ∞。
  • 把 s 的 neighbor 标成 1
  • 再找已经标成 neighbor 的 node，再去找他们的 neighbor，如果是 ∞ 的话，就换成 2。
  • 持续做到全部做完为止。
  • implement:

  

  
  #include<iostream>
  using namespace std;
  
  const int MAX_NODE_CNT = 10;
  
  // Input:
  // - adjacent: the adjacency matrix
  // - nodeCnt: number of nodes
  // - source: the source nodes- dist: to store the distance from the source
  // This function will find the distances from the source node to each node and put them in "dist"
  void distFromSource(const bool adjacent[][MAX_NODE_CNT], int dist, int nodeCnt, int source);
  
  int main()
  {
  	int nodeCnt = 5;
  	bool adjacent[MAX_NODE_CNT][MAX_NODE_CNT] 
  	= {{1, 1, 0, 0, 1}, {1, 1, 1, 0, 0}, {0, 1, 1, 1, 0}, {0, 0, 1, 1, 1}, {1, 0, 0, 1, 1}};
  /*
  	   1, 1, 0, 0, 1
  	   1, 1, 1, 0, 0
  	   0, 1, 1, 1, 0
  	   0, 0, 1, 1, 1
  	   1, 0, 0, 1, 1
  */
  	int dist[MAX_NODE_CNT] = {0}; //store result
  	int source = 0;
  
  	distFromSource(adjacent, dist, nodeCnt, source)
  
  	cout << "nThe complete result: n";
  	for (int i = 0; i < nodeCnt; ++i)
  	{
  		cout << dist[i] << " ";
  	}
  
  	return 0;
  }
  
  void distFromSource(const bool adjacent[][MAX_NODE_CNT], int dist, int nodeCnt, int source)
  {
  	for (int i = 0; i < nodeCnt; ++i)
  		dist[i] = nodeCnt; //find a large number
  
  	dist[source] = 0;
  	int curDist = 1; // current dist
  	int complete = 1; //record how many node is labeled
  
  	while(complete < nodeCnt){
  		for (int i = 0; i < nodeCnt; ++i){ // one for a level [1:neighbor -> 2. neighbors' neighbors ->...]
  			if (dist[i] == curDist - 1){// 1: 1; 2: 2; 3: 3;...
  				for (int j = 0; j < nodeCnt; ++j){ // from i to j
  					if(adjacent[i][j] == true && dist[j] == curDist){
  						dist[j] = curDist;
  						complete++;
  					}
  				}	
  			}
  		}
  		curDist++; // dist increase when level++
  	}
  }
  
  

上面程序就是依照 想法 写出来的。

Complexity:

那我们来算算看这个 algorithm 的 complexity吧!

• 有三层loop (n = nodeCnt)
  • 有两层 for loop → O(n^2)
  • while loop → worst-case: 跑 n 次 O(n)

所以这个 algorithm 的 complexity 是 O(n^3) 吗????????????????

吗????

其实不然，请听我娓娓道来:

• inner loop 只有在 label == curDist - 1的时候才会启动
• 每一个 node 最终就只会属於一个 level → 一个 node 只会启动 inner loop 恰一次
• 因此在 worst-case 中，while loop 还有第一个 for loop 只会得到 O(n^2)
• 而inner loop 则会给到 O(n^2)

因此最後只会得到 O(n^2 + n^2) → O(n^2)

breadth-first search(BFS):

简单说就是 广度优先，先找附近的，一层一层找

→ 甚至可以用更低的 complexity : O(n+m) → 使用的是 "quene" 的 data structure。

depth-first search(DFS):

也就是深度优先。

My Opinion

这次的课程牵扯到十分多数学的概念，让我这个三类仔有点招架不住，但还是很努力的把她听懂了...

虽然理解的慢，但理解之後好像海阔天空了(还是我会错意?，可能以後会遇到更难的)

Q: Please find anyone who is not telling the truth.