Introduction (Concepts, Recursion, Algorithm Analysis) 學習筆記

[Fionn88]

• NYCU 資料結構 Data Structure – 101學年度 | 資訊工程學系 彭文志老師
• PDF 講義索取

[Fionn88]

Overview: System Life Cycle

• Requirements

搜索引擎

1. 把所有網頁撈回來
2. 分析網頁內容，去建關鍵字和 index

3. 使用者下 query，把 document 去做 metric 並把資料抓出來顯示

   • Analysis

     • Bottom-up
     • Top-down

       當你設計一個系統，思考他的 input 跟 output 是什麼

   • Design

     • Data objects：abstract data types

       這些 Data objects 所實現的 function 是什麼

     • Operations：specification & design of algorithms

       Function：設計演算法來達到

• Refinement & Coding
  • Choose representations for data objects
  • Write algorithms for each operation on data objects
• Verification
  • Correctness proofs: selecting proved algorithms
  • Testing: correctness & efficiency

    各種 Test Case 看正確性跟有效性

  • Error removal: well-document

    回傳 Error Code 並且寫註解

Yahoo 新聞首頁

一個 Team 做出來的，並且來自各國，EX: 印度, 美國, etc.

• 啟動備份新聞平台去測試小功能 => Testing

[Fionn88]

Evaluative judgments about programs

• Meet the original specification?

  是否有符合預期的規格

• Work correctly?

  是否正常的運作

• Document?

  有無寫文件

• Use functions to create logical units?

  每個 Data object 對應到的 function 是否可以運作

• Code readable?

  Code 是否看得懂

• Use storage efficiently?

  儲存是否有效率（雖然說現今儲存很便宜，但是如果是行動裝置的話，對於應用程式的儲存更要求）

• Running time acceptable?

  通常愈快愈好，愈小愈好（較為主觀）

[Fionn88]

Data Abstraction

• Predefined & user defined data type

Struct student { char last_name;
int student_id;
char grade; }

• Data type: objects & operations

integer: +, -, *, /, %, =, ==, atoi()

• Representation: char 1 byte, int 4 bytes

• Abstract Data Type (ADT): data type specification(object & operation) is separated from representation.

• ADT is implementation-independent

  也就是外部類別只需要呼叫介面提供的方法，不用也不需要知道內部如何實作

[Fionn88]

Algorithm Specification

解決問題的方法

• Algorithm criteria
  • Input
  • Output

    反應出你的問題是什麼

  • Definiteness

    解決問題的目的

  • Finiteness

    有限的步驟去達成，會停止

  • Effectiveness

    有效率的做法

program doesn’t have to be finite (e.g. OS scheduling)

[Fionn88]

Example 1: Selection Sort

從小到大的排序，選最小的出來，放到第一個 有兩個 Set 的數字，一個是已排序，一個是 unsort.

void sort(int list[ ], int n)
{
for (i=0; i < n-1; i++) {
min = i;
for (j = i+1; j < n; j++) {
if (list[j] < list[min])
min = j; }
SWAP(list[i], list[min], temp);
}
}

如是 comparison base 的話是 Quick Sort 是最快的：O(nlogn)，非 comparison base 的話則是 Radix Sort

[Fionn88]

Example of Binary Search

前提數字是排好序的

input：你想找的數字 output：數字是否有在這個 List

Binary Search 跟 Binary Search Tree 是不同的東西

int compare(int x, int y)
/* return -1 for less than, 0 for equal */
int binsearch(int list[], int searchno, int left, int right)
{
while (left <= right) {
middle = (left + right) / 2;
switch ( COMPARE(list[middle], searchno) ) {
case -1: left = middle +1;
break;
case 0: return middle;
case 1: right = middle -1;
}
}
}

[Fionn88]

Example 3: Selection Problem

• Selection problem: select the kth largest among N numbers input：找第幾大的數字 output：該位數字

• Solutions

  • Approach 1
  • read N numbers into an array
  • sort the array in decreasing order
  • return the element in position k
  • Approach 2
  • read k elements into an array
  • sort them in decreasing order
  • for each remaining elements, read one by one
    • ignored if it is smaller than the kth element
    • otherwise, place in correct place and bumping one out of array

[Fionn88]

Recursive Algorithms

• Direct recursion: functions that call themselves

• Indirect recursion: Functions that call other functions that invoke calling function again

• C(n,m) = n!/[m!(n-m)!] ⇒ C(n,m)=C(n-1,m)+C(n-1,m-1)

• Boundary condition for recursion

  呼叫自己停的條件為什麽

• n! = n × (n-1)! ⇒fact(n) = n × fact(n-1) 0 ! = 1

  int fact(int n)
  { if ( n== 0)
  return (1);
  else
  return(n*fact(n-1));
  }

Recursive Multiplication

• a × b = a × (b-1) + a a × 1 = a

  int mult(int a, int b)
  { if ( b== 1)
  return (a);
  else
  return( mult(a, b-1) + a );
  }

[Fionn88]

不同的 Data structure 實作演算法（解決問題的方式）時會有不同的複雜度

Recursive Summation

空間複雜度為：O(N)。

• sum(1, n) = sum(1, n-1) + n sum(1, 1) = 1

  int sum(int n)
  { if ( n== 1)
  return (1);
  else
  return( sum(n-1) + n );
  }

For Loop 去解決加總演算法的話，空間複雜度為：O(1)。

時間複雜度：Recursive Summation > For Loop

Recursive binary search

int binsearch(int list[], int searchno, int left, int right)
{
if (left <= right) {
middle = (left + right)/2;
switch (COMPARE(list[middle], searchno) )
{
case -1: return binsearch(list, searchno, middle+1, right)
case 0: return middle;
case 1: return binsearch(list, searchno, left, middle-1);
}
}
return -1;
}

Recursive Permutations

• Permutation of {a, b, c} (a, b, c), (a, c, b) (b, a, c), (b, c, a) (c, a, b), (c, b, a)
• Recursion?
  • a+Perm({b,c})=> {a, b, c} and {a, c, b}
  • b+Perm({a,c})=> {b, a, c} and {b, c, a}
  • c+Perm({a,b})=> {c, a, b} and {c, b, a}

void perm(char *list, int i, int n)
{
if ( i == n) {
for (j=0; j <=n; j++)
cout<<list[j];
}
else {
for (j = i; j <= n; j++) {
SWAP(list[i], list[j], temp);
perm(list, i+1, n);
SWAP(list[i], list[j], temp);
}
}
}

[Fionn88]

Performance Evaluation

• Performance analysis: machine independent

  跟機器沒有關係

• Performance measurement: machine dependent

  跟機器有關係

Performance Analysis

• Complexity theory
• Space complexity: amount of memory
• Time complexity: amount of computer time

[Fionn88]

Space Complexity

• S(P) = c + Sp(I)

c: fixed space(instruction, simple variables, constant

存放變數的 storage，與怎麼實作演算法叫有關係

Sp(I): depends on characteristics of instance I

Sp(I)：Input 的量的大小

Characteristics: number, size, values of I/O associated with I

if n is the only characteristic, Sp(I) ⇒ Sp(n)

[Fionn88]

Time Complexity

• T(P) = c + Tp(I)

c: compile time Tp(I): program execution time depends on characteristics of instance I

Characteristic: number, size, values of I/O associated with I

predict the growth in run time as the instance characteristics change

• Compile time (C) independent of instance characteristics
• Run (execution) time Tp TP(n)=caADD(n)+csSUB(n)+clLDA(n)+cstSTA(n)
• Definition A program step is a syntactically or semantically meaningful program segment whose execution time is independent of the instance characteristics.

[Fionn88]

Some Rules

• Rule 1: If T1(N)=O(f(N)) and T2(N)=O(g(N)) Then (a) T1(N)+T2(N) = max ( O(f(N)), O(g(N)) ) (b) T1(N)T2(N) = O( f(N)g(N) )
• Rule 2: If T(N) is a polynomial of degree k, then T(N)=Θ(Nk)
• Rule 3: (logN)k=O(N) (Prove it in our discussion board)