Data structure & algorithms 數據結構與演算法~入門筆記 (1)

introduction to algorithms

Every algorithm must satisfy five requirements:
1. Input: Externally supplied data quantity > 0
2. Output: Produced data quantity $\geq$ 1
3. Definiteness: each instruction must be unambiguously defined.
4. Finiteness: Algorithm must terminate after some finite number of steps (Note that a program can run for infinite time, such as in case of an infinite loop)
5. Effectiveness: each instruction must basic enough such that it can be, in principle, done by a person with pencil and pen to verify. In other words, it is feasible. (Note, correctness is not part of effectiveness; A defined algorithm need not to be correct).

To judge the performance of an algorithm, two things to look for:

1. Space complexity: How much storage space is taken for algorithm to finish
2. Time complexity: How much time is taken for algorithm to finish
   Time complexity is more of a concern. To calculate:
   S/E(Steps per Execution): How much steps are needed to operate the given instruction one time.
   Frequency: How many repetition of the instruction.
   Total = S/E * Frequency
   For example, for a given integer $n$:

int SumProgram (int n){
    int i, sum;
    sum = 0; #S/E= 1, f=1, Total=1 
    for (i=1, i<=n, i++){ #S/E=3, f=n+1, Total=3(n+1)
    sum= sum+i; #S/E=1, f=n, Total=n
    }
    return sum; #S/E=1, f=1, Total=1
}

Thus, adding up, the total time taken is 1+ 3($n$+1) + $n$ + 1 = 4$n$+5.
The time scales linearly as $n$.
The time complexity is O(4$n$+1)=O($n$).
Other examples include time growing exponentially as $n$, which is: O($n^2$).

sorting

We need to sort out the data before doing things like searching or matching.

Common sorting algorithms:

• Bubble Sort:
  • Used to sort sequence of numbers.
  • Start at the right end of the sequence, compare the two numbers located at the end. 8 6 35 2 9 4 $\rightarrow$ If the number on right is smaller than the number on left. $\rightarrow$ Swap the numbers 8 6 3 5 2 4 9 . Otherwise leave them as before.
  • Moving on to the next two numbers: 8 6 3 5 2 4 9. Repeat the same method.
  • After going through the sequence once, the smallest number should be left-most: 2 8 6 3 54 9. Now this number is considered fully sorted and won’t participate in further sorting.
  • Repeat again the same method starting from the two numbers on the right end. 2 8 6 3 5 49.
• Selection sort 
• Insertion Sort
• Heap Sort
• Shell Sort
• Merge Sort
• Quick Sort
• Binary tree, radix…