算法设计与分析笔记0x00 —— 课程介绍及基础知识

此系列算法设计笔记基于 ShanghaiTech CS240 Fall2017 算法设计与分析课程。
相较算法基础课程,更加偏向于数学分析。
computational tractability: 计算的可追踪性,即可用数学语言进行推理证明

Notation Properties

算法导论的笔记中提到了其可传递性,在这里补充上可加性。

  • If f = O(h) and g = O(h) then f + g = O(h).
  • If f = Ω(h) and g = Ω(h) then f + g = Ω(h).
  • If f = Θ(h) and g = O(h) then f + g = Θ(h).

Continue reading “算法设计与分析笔记0x00 —— 课程介绍及基础知识”

算法基础笔记0x01 —— 算法分析

focus on speed

时间复杂度

  • Time complexiy of algorithm is number of steps it takes before it terminates.
    • 在算法终止之前操作的步数
  • Issue 1: Number of steps depends on input size
    • Analyze complexity as a function of input size
  • Issue 2: Even for a fixed size, the running time can vary
    • Consider worst case
    • Sometimes we consider average case
      • but we don’t know how the input are distributed
  • Issue 3: What counts as a step?
    • Eg: check for a word. Step is checking one word or a page.
    • we need to user a coarse-grained model, ignore minor details and focus on big picture.
    • 此处粗粒度模型,可简单理解为将复杂系统简化

Continue reading “算法基础笔记0x01 —— 算法分析”