算法(1)-渐进表示(本节无算法)

杂谈

• 授课形式: 每周三个学时, 讲解基本理论和方法;
• 上机27学时: 45分钟习题课, 45分钟上机实践;
• 课程作业: 每周一次(一道题)+大作业+思考题;
• 考核:
  • 期末考试: 35%;
  • 期中考试: 30%;
  • 平时作业+上机作业: 15% +思考题
  • 大作业: 10%;
  • 出勤+随堂: 10%;
• 教材: 算法导论(中英结合);
• 参考书:
  • 计算机程序设计艺术 Don
  • 算法设计与分析基础 A L
  • 公开课: 网易公开课 算法导论 MIT OCW算法;
• 联系方式: 信息学院 126B zhewei@ruc.edu.cn

谈日程

• 老三篇 排序 搜索 贪心, 动态规划
• 期中考以后是高级的算法, 图算法, 矩阵运算, 快速变换, 数论算法 (之前的都是机器学习和挖掘),NP类;

目标

• 怎么设计算法,
• 怎么分析算法,
• 怎么比较算法好坏;

渐进表示(Asymtoptic representation)

1. 两个计算时间为函数f(n), g(n); 给出算法的执行时间:

上界函数 big O

2. 定义1: 如果有两个正常数c和n0, 使得对所有的n>=n0的时候, 有0<=f(n)<=c*g(n) //左边小于等于右边的阶级;
   g(n)为f(n)的上界函数;

• 上界函数有如下运算性质:
  • O(f) + O(g) = O(max(f, g));
  • O(f)O(g) = O(fg);
  • f = O(f);
  • O(Cf(N))= O(f(N));
  • 大O比率定理: f(n) = O(g(n)), 存在C>0 和某个n0, 使得所有n>n0, 有f(n)/g(n)<=C; 因此lim f(n)/g(n) <=c;
  • 证明的时候: 就是让整个算式 除以 n^max; 极限的时候其他都会变成0
  • 最重要是应用;
  • O(1) < O(logn) < O(n) < O(nlogn) < O(n^2);
  • 2^n < n! < n^n;
  • n! == sqrt(2PIn)*(n/e)^n;

Ω 下界函数 big Omega

• 定义: 如果存在两个正常数c 和 n0, 使得对所有的n>=n0, 有 f(n)>=c|g(n)| //左边的阶级大于等于右边的阶级
• 大Ω比率定理: f(n) = O(g(n)), 存在C>0 和某个n0, 使得所有n>n0, 有gn/f(n)<=C(上下相反了); 因此lim g(n)/f(n) <=c;

theta 平均情况

-被两条线给夹住了; 因此要求必须同阶级;
-3n^2+5=O(n3); but 3n^2+5!=theta(n3);

小o和小Ω

-f(n)/g(n)<e (e为任何>0的数) 换句话说, 去掉了Big O中的同阶级情况; 可以读作"fn阶级低于gn";
-g(n)/f(n)<e ,去掉了Big Ω中的同阶级, fn阶级高于gn;

整数求和公式的时间复杂度

常用的时间复杂度表格

1. Σ<1~n>( i ) 的时间复杂度: n^2;

因为这是一个等差数列, 所以Sn = (n+1)*n/2

2. Σ i^k的时间复杂度: n^(k+1)

对Σi^k/n(k+1)求极限, 运用洛必达法则, 解出是一个常数, 所以得出是theta(n^(k+1));

3. n!的时间复杂度 stirling公式: (n/e)^n;

推导: n! == sqrt(2PIn)*(n/e)^n;

4. Σ 1/i的时间复杂度=logN

证明使用调和级数, 假设x = Σ 1/i; 那么x>=2的时候, Sx=1+1+2+4+8+...-1=2^x-1; 那么也就是说,在原先Σ 1/i中,当和为x的时候, 需要有n=2^x-1项; 所以x=log(n+1) = O(logn);

---

• 作业3.1-7