雜談
- 授課形式: 每周三個(gè)學(xué)時(shí), 講解基本理論和方法;
- 上機(jī)27學(xué)時(shí): 45分鐘習(xí)題課, 45分鐘上機(jī)實(shí)踐;
- 課程作業(yè): 每周一次(一道題)+大作業(yè)+思考題;
- 考核:
- 期末考試: 35%;
- 期中考試: 30%;
- 平時(shí)作業(yè)+上機(jī)作業(yè): 15% +思考題
- 大作業(yè): 10%;
- 出勤+隨堂: 10%;
- 教材: 算法導(dǎo)論(中英結(jié)合);
- 參考書:
- 計(jì)算機(jī)程序設(shè)計(jì)藝術(shù) Don
- 算法設(shè)計(jì)與分析基礎(chǔ) A L
- 公開課: 網(wǎng)易公開課 算法導(dǎo)論 MIT OCW算法;
- 聯(lián)系方式: 信息學(xué)院 126B zhewei@ruc.edu.cn
談日程
- 老三篇 排序 搜索 貪心, 動(dòng)態(tài)規(guī)劃
- 期中考以后是高級的算法, 圖算法, 矩陣運(yùn)算, 快速變換, 數(shù)論算法 (之前的都是機(jī)器學(xué)習(xí)和挖掘),NP類;
目標(biāo)
- 怎么設(shè)計(jì)算法,
- 怎么分析算法,
- 怎么比較算法好壞;
漸進(jìn)表示(Asymtoptic representation)
- 兩個(gè)計(jì)算時(shí)間為函數(shù)f(n), g(n); 給出算法的執(zhí)行時(shí)間:
上界函數(shù) big O
- 定義1: 如果有兩個(gè)正常數(shù)c和n0, 使得對所有的n>=n0的時(shí)候, 有0<=f(n)<=c*g(n) //左邊小于等于右邊的階級;
g(n)為f(n)的上界函數(shù);
- 上界函數(shù)有如下運(yùn)算性質(zhì):
- 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 和某個(gè)n0, 使得所有n>n0, 有f(n)/g(n)<=C; 因此lim f(n)/g(n) <=c;
- 證明的時(shí)候: 就是讓整個(gè)算式 除以 n^max; 極限的時(shí)候其他都會變成0
- 最重要是應(yīng)用;
- O(1) < O(logn) < O(n) < O(nlogn) < O(n^2);
- 2^n < n! < n^n;
- n! == sqrt(2PIn)*(n/e)^n;
Ω 下界函數(shù) big Omega
- 定義: 如果存在兩個(gè)正常數(shù)c 和 n0, 使得對所有的n>=n0, 有 f(n)>=c|g(n)| //左邊的階級大于等于右邊的階級
- 大Ω比率定理: f(n) = O(g(n)), 存在C>0 和某個(gè)n0, 使得所有n>n0, 有g(shù)n/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的數(shù)) 換句話說, 去掉了Big O中的同階級情況; 可以讀作"fn階級低于gn";
-g(n)/f(n)<e ,去掉了Big Ω中的同階級, fn階級高于gn;
整數(shù)求和公式的時(shí)間復(fù)雜度
常用的時(shí)間復(fù)雜度表格
- Σ<1~n>( i ) 的時(shí)間復(fù)雜度: n^2;
因?yàn)檫@是一個(gè)等差數(shù)列, 所以Sn = (n+1)*n/2
- Σ i^k的時(shí)間復(fù)雜度: n^(k+1)
對Σik/n(k+1)求極限, 運(yùn)用洛必達(dá)法則, 解出是一個(gè)常數(shù), 所以得出是theta(n^(k+1));
- n!的時(shí)間復(fù)雜度 stirling公式: (n/e)^n;
推導(dǎo): n! == sqrt(2PIn)*(n/e)^n;
- Σ 1/i的時(shí)間復(fù)雜度=logN
證明使用調(diào)和級數(shù), 假設(shè)x = Σ 1/i; 那么x>=2的時(shí)候, Sx=1+1+2+4+8+...-1=2^x-1; 那么也就是說,在原先Σ 1/i中,當(dāng)和為x的時(shí)候, 需要有n=2^x-1項(xiàng); 所以x=log(n+1) = O(logn);
- 作業(yè)3.1-7
