三大类CS算法的总结

根据我们之前的post–why数据结构与算法中写道

基于用途对算法分类(参考Princeton CS算法课程):

Sorting algorithm
Searching algorithm
Graph algorithm

Recursive and iterative algorithm的区别

  • Both repeatedly execute the set of instructions. 通常我们尽量避免使用recursion, 而更倾向于使用iteration。
  • Recursion: when a statement in a function calls itself repeatedly.
    • 格式: 总共有2 parts.
      • A base case: The base case defines the termination condition.
      • The general recursive case: The general case where it calls itself.
    • Infinite recursion can crash the system because it uses a stack.
    • 速度: Slow in execution.
  • Iteration: when a loop repeatedly executes until the controlling condition becomes false.
    • 格式: 总共有4 parts. Initialization, termination condition, execution of statement within the loop, and update the control variable.
    • Infinite loop uses CPU cycles repeatedly because it does not use a stack.
    • 速度:Fast in execution.

Sorting algorithm

Sort a list or array of $n$ elements, and the smallest one is to put on the left, the largest one on the right.

  • Bubble Sort:Starting on the left, compare adjacent items and keep “bubbling” the larger one to the right (it’s in its final place). Bubble sort the remaining $n -1$ items. [Best: O(n), Worst:O(N^2)]

Searching algorithm

Graph algorithm

Leave a Comment