Skip to content

算法设计与分析 - NJU

课程简介

  • 所属大学：南京大学
  • 先修要求：程序设计，数据结构与算法
  • 编程语言：C,CPP

课程资源

课程笔记

计算模型

L1：计算模型

Algorithm - the spirit of computing

Model of Computation: Machine- and language- independent algorithms, running on an abstract machine

数学归纳法：弱归纳（n 仅仅依赖于 n - 1）；强归纳（n 依赖于 1 至 n - 1 所有）

算法设计与分析-NJU-1.png

Algorithm Analysis: worst case, average case...

  • How to measure（抽象地）: machine independent, language independent, programming independent, implementation independent
  • Amout of work done（问题规模）：\(n \Rightarrow AA \Rightarrow f(n)\)
  • Critical operations（关键操作）

算法设计与分析-NJU-2.png

L2：渐进时间复杂度（Asymptotic Behavior）

Reiative Growth Rate（相对增长率）

算法设计与分析-NJU-3.png

  • 三种符号对应三种集合，\(g\) 为渐进增长率（函数）

  • \(log(n)\) 是一个档位，可以代表 \(2log(n)\)，\(3log(n)\) 等等

Big Oh

算法设计与分析-NJU-4.png

  • 更多地关注 n 较大的情况

  • \(f\notin O(g)\), if c is \(+ \infty\)

Asymptotic Growth Rate（渐进增长率）：\(log(n)<n<nlog(n)<n^k<2^n\)

Big \(\varOmega\)

  • 定义形式同上

The Set \(\Theta\)

算法设计与分析-NJU-5.png

集合性质

  • 传递性：if \(f\in O(g)\) and \(g \in O(h)\) , then \(f \in O(h)\)

  • 对称性 ：\(f\in O(g)\) if and only if \(g\in \varOmega(f)\)；\(f\in \Theta(g)\) if and only if \(g\in \Theta(f)\)

  • 加法：\(O(f+g)=O(max(f,g))\)

Little Oh，\(\omega\)

  • 区别与 Big , 没有等于号
  • \(\lim_{n \to \infty}=0\)
  • $\lim_{n \to \infty}=+ \infty $

dsf