算法基础笔记0x00 —— 基本概念和基础数学

这一系列算法笔记基于 ShanghaiTech CS140 Fall2017 算法基础课程。

  • Course structure
    • Intro and math review
    • Analysis of algorithms
    • Sorting
    • Search
    • Divide and conquer
    • Greedy algorithms
    • Graphs
    • Dynamic programming
    • NP
    • String algorithms

  • Reference
    • Introduction to Algorithms

Comparing Algorithms

  • 最基本的认知
    • 时间远远重要于空间
    • 算法的优化远比硬件性能的提高效果来得明显
  1. Time and memory
  2. Can algorithms parallelized
  3. How much energy does it use
  4. Subjective measures. simplicity and elegance

Sizes of Functions

三种常见形式的复杂度表达式

  • Polynomials 多项式
  • Exponentials 指数形式
  • Logarithms 对数形式

一些事实

  • Fact1: If b > 1, then $b^x$ eventually dominates any polynomial $f(x)$.
    • 指数表达式终将领先于多项式
  • Fact2: $$\lim_{x\to\infty}\frac{b^x}{f(x)}$$
  • Fact3: If k > 0, then $x^k$ eventually dominates $log_b(x)$ for any b > 1
    • 多项式表达式终将领先于对数表达式
  • Fact4: $$\lim_{x\to\infty}\frac{x^k}{log_b(x)} = \infty$$

exponential > polynomial > log

Basic Math

  • Arithmetic series
    • 等差级数
  • Geometric series
    • 等比级数
  • Induction
    • It consists of base step and inductive step.
    • Base step Prove S(1) is true.
    • Inductive step Prove that if S(n) is true, then S(n+1) is true.

Leave a Reply

Your email address will not be published.