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

• 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.