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.