杂谈
- 授课形式: 每周三个学时, 讲解基本理论和方法;
- 上机27学时: 45分钟习题课, 45分钟上机实践;
- 课程作业: 每周一次(一道题)+大作业+思考题;
- 考核:
- 期末考试: 35%;
- 期中考试: 30%;
- 平时作业+上机作业: 15% +思考题
- 大作业: 10%;
- 出勤+随堂: 10%;
- 教材: 算法导论(中英结合);
- 参考书:
- 计算机程序设计艺术 Don
- 算法设计与分析基础 A L
- 公开课: 网易公开课 算法导论 MIT OCW算法;
- 联系方式: 信息学院 126B zhewei@ruc.edu.cn
谈日程
- 老三篇 排序 搜索 贪心, 动态规划
- 期中考以后是高级的算法, 图算法, 矩阵运算, 快速变换, 数论算法 (之前的都是机器学习和挖掘),NP类;
目标
- 怎么设计算法,
- 怎么分析算法,
- 怎么比较算法好坏;
渐进表示(Asymtoptic representation)
- 两个计算时间为函数f(n), g(n); 给出算法的执行时间:
上界函数 big O
- 定义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 平均情况
-被两条线给夹住了; 因此要求必须同阶级;
-3n2+5=O(n3); but 3n2+5!=theta(n3);
小o和小Ω
-f(n)/g(n)<e (e为任何>0的数) 换句话说, 去掉了Big O中的同阶级情况; 可以读作"fn阶级低于gn";
-g(n)/f(n)<e ,去掉了Big Ω中的同阶级, fn阶级高于gn;
整数求和公式的时间复杂度
常用的时间复杂度表格
- Σ<1~n>( i ) 的时间复杂度: n^2;
因为这是一个等差数列, 所以Sn = (n+1)*n/2
- Σ i^k的时间复杂度: n^(k+1)
对Σik/n(k+1)求极限, 运用洛必达法则, 解出是一个常数, 所以得出是theta(n^(k+1));
- n!的时间复杂度 stirling公式: (n/e)^n;
推导: n! == sqrt(2PIn)*(n/e)^n;
- Σ 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
