数据结构基础(二)

Chapter 1 Algorithm Analysis

Algorithm

An algorithm must satisfy

• input 0 or more input
• output at least 1 output
• definiteness clear and unambigeous
• finiteness terminate after finite number of steps
• effectiveness

 

What to analyze

Time complexity

tips: return;, a=1; should be counted when using T(N)

Asymptotic Notation

• $T(N) = O(f(N)), T(N)\le c\cdot f(N), \forall N>n_0(smallest)$
• $T(N) = \Omega(g(N)), T(N)\ge c\cdot g(N), \forall N>n_0(largest)$
• $T(N) = \Theta(h(N)), T(N)= O(h(N))$
• $T(N) = o(p(N)),if\ T(N)=O(p(N))\ and\ T(N)\ne\Theta(p(N))$

[Eg1] Matrix addition

void add( int a[][ MAX_SIZE ], int b[][ MAX_SIXE ], int c[][ MAX_SIZE ], int rows, int cols){
  int i,j;
  for( i = 0; i < cols; ++i){
    for( j = 0; j < rows; ++j){
      c[i][j] = a [i][j] + b[i][j];
    }
  }
}

$T(rows,cols)=2rows\cdot cols+2rows+1$

$O(rows,cols)=rows\cdot cols$

[Eg2] Summing a list of numbers (iterative)

float sum( float list[], int n ){
  float temp_sum = 0; // count = 1
  int i;  // no add count
  for( i = 0; i < n; ++i ){ // count += 1
    temp_sum += list[i];  // count += 1
  }
  return temp_sum;  // count += 1
}

$T_{sum}(n)=2n+3$

[Eg3] Summing a list of numbers (recursive)

float sum( float list[], int n ){
  if( n ){ // count = 1
    return sum( list, n-1 ) + list[n-1];  // count += 1
  }
  return 0;  // count += 1
}

$T_{sum}(n)=2n+2$

Space complexity

 

Compare the Algorithms

[Eg] Max Subsequence Sum Problem Given integers $A_1$, $A_2$, …, $A_n$, find the maximum value of sum from $A_i$ to $A_j$

1. Algo.1

for i: n
  for j: n
    sum for k: i->j
    compare sum

$T(N) = O(N^3)$

2. Algo.2

for i: n
  for j: i->n
    sum i->j
    compare sum with max_sum

$T(N) = O(N^2)$

Storing to cut off calculatation

3. Algo.3 ( Divide & Conquer )

def MSS( sequnce a[n], int start, int end ):
  if length <= 1 :  return a[n]
  left = MSS (a, start, mid)
  right = MSS (a, mid, end)
  total = max_sum for mid->end + max_sum for mid->start
  return max( left, right, total )

$T(N)=2T(N/2)+cN,T(1)=O(1)$

$\Rightarrow T(N) = O(N\log N)$

Algo.4 ( DP )

state transition equation

$$maxSum[i] = \begin{cases}sequence[i]+maxSum[i-1]&sequence[i]>0\\\\0&sequence[i-1]+maxSum[i-1]<0\end{cases}$$

$$result=\mathrm{max}(maxSum)$$

$T(N) = O(N)$

 

Logarithms in the Runing Time

Eg Binary Search

requirement: static & sorted

$T(N) = O(\log N)$

 

Checking Your Analysis

• Method 1: try

• Method 2: calculate, use limit