随笔2019-4-1

算法课

渐进符号介绍
如何求解递归式

渐进符号

大O符号

$f(n)=O(g(n))$ : there are consts $c>0, n_0>0$ such that $0\le f(n)\le c \cdot g(n)$ for all $n\ge n_0$
例子: $2n^2 =O(n^3)$ O()意味着小于或等于

$O(g(n))$ 又可视为函数集 $\{ f(n)|0\le f(n)\le c \cdot g(n)，n>n_0\}$
因此 $2n^2 \in O(n^3)$

More convention(惯例、宏)

Example(后面用Ex替代). $f(n)=n^3+O(n^2)$ 等价于存在 $h(n)\in O(n^3)$ 使得 $f(n)=n^3+h(n)$
Ex. $n^2+O(n)=O(n^2)$ 等号左右两边的式子是不允许掉换的，即不对称的

$\Omega$ 符号

与大O相反, $\Omega$ 确定了下界
$f(n)=\Omega(g(n))$ : there are consts $c>0, n_0>0$ such that $f(n)\ge c \cdot g(n)$ for all $n\ge n_0$
$\Omega(g(n))$ 又可视为函数集 $\{f(n)\ge c \cdot g(n), n>n_0\}$

Ex. $\sqrt{n}=\Omega(lgn)$ 由高中数学可知 $\sqrt{n}$ 处于 $lgn$ 上方

$O:\le \quad \Omega: \ge \quad \Theta: =$

$\Theta(g(n))=O(g(n)) \bigcap \Omega(g(n))$

硬约束

$o: <$ 和 $\omega: >$ 与大写符号存在一个常数c不同，小写符号要求对所有c成立， $n_0$ 要依赖于c

Ex. $2n^2=o(n^3) \quad (n_0=\frac{2}{c})$ 由函数图像可知，当 $n>n_0$ 时，对于所有c， $2n^2 < c\cdot n^3$ 成立

Ex. $\frac{1}{2}n^2=\Theta(n^2)\not=o(n^2)$ 由于没有交点，故找不到对应的 $n_0$

解递归式

具体有三种方法，需要注意的一点是递归问题没有通用的解法

代换法

1.猜答案: 猜形式
2.用归纳验证
3.解得常数

Ex. $T(n)=4T(\frac{n}{2}) + n$ 首先这个问题的答案是 $\Theta(n^2)$ 且 $T(1)=\Theta(1)$
用代换法解该例子

猜 $T(n)=O(n^3)$
设 $T(k)\le ck^3$ for $k < n$ 已经成立
$T(n)=4T(\frac{n}{2})+n\le 4c(\frac{n}{2})^3 +n=cn^3-(\frac{1}{2}cn)$
可以发现当 $\frac{1}{2} cn^3-n\ge 0$ 时成立，即 $c\ge2, n\ge1$

当猜 $T(n)=O(n^2)$ 时，用同样的过程但无法使得 $-n\ge0$ ，可见需要使用其他方法
因此不能简单的用 $ck^2$ , 而是

猜 $T(k)\le c_1k^2-c_2k$ for $k < n$
$T(n) \\= 4T(\frac{n}{2})+n\\=4[c_1(\frac{n}{2})^2-c_2(\frac{n}{2})]+n\\=c_1n^2+(1-2c_2)n\\=c_1n^2-c_2n-(-1+c_2)n$
若要让 $(-1+c_2)n\ge0$ 则 $c_2\ge1$
同时要考虑到base case。 $T(1)\le c_1-c_2$ 因为 $c_2\ge1$ 所以 $c_1$ 要足够大才能 $T(1)=\Theta(1)$

递归树法

由于主要是图的形式，而图暂时还没弄好，故建议这部分看《算法导论》

主方法

特点是只能应用到特定的递归式上，形式如 $T(n)=aT(\frac{n}{b})+f(n)$
其中 $a\ge1$ (意味着至少递归一次), $b>1$ , $f(n)$ 渐进趋正(对于足够大的n, f(n)为正)

通过比较 $f(n)$ 与 $n^{log_b{a}}$ (递归树节点的数量)分为3种情况：
(注：本来直观上树节点的数量应该是 $a^{log_b{n}}$ ，每层增加a倍，总共 $log_b{n}$ 层，利用换底公式变成上面的样子)

-Case1

$f(n)=o(n^{log_b{a} - \epsilon})$ for some $\epsilon > 0$ (多项式小于)
此时 $T(n)=\Theta(n^{log_ba})$

-Case2

$f(n)=o(n^{log_b{a}}lg^kn)$ for some $k \ge 0$
此时 $T(n)=\Theta(n^{log_ba}lg^{k+1}n)$

-Case3

$f(n)=o(n^{log_b{a} + \epsilon})$ for some $\epsilon > 0 \quad \& \quad af(\frac{n}{b}) \le (1-\epsilon')f(n)$ for some $\epsilon' > 0$ (主要保证递归过程中 $f$ 在变小)
此时 $T(n)=\Theta(f(n))$

例子

Ex. $T(n) = 4T(\frac{n}{2}) + n$
注意到a = 4, b = 2, 即 $n^{log_b{a}}=n^2$ 以及 $f(n)=n$
可知应该属于Case1，代入得 $T(n)=n^2$

Ex. $T(n) = 4T(\frac{n}{2}) + n^2$
与上面例子同理，但考虑到Case1的 $\epsilon$ 无法取0，故属于Case2，得 $T(n)=n^2lgn$

Ex. $T(n) = 4T(\frac{n}{2}) + n^3$
同理该例子属于Case3, $T(n)=n^3$

Ex. $T(n) = 4T(\frac{n}{2}) + \frac{n^2}{lgn}$
该例子则找不到Case符合，因为Case2要求 $k\ge0$ ，该例子中k=-1

主方法的具体证明则不在此介绍，需要的可以翻翻《算法导论》

(看在敲公式敲了一下午的份上，希望有缘的你看完可以点个喜欢)

最后编辑于：2019.04.16 21:12:52

人面猴
序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
沈念sama阅读 214,444评论 6赞 496
死咒
序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
沈念sama阅读 91,421评论 3赞 389
救了他两次的神仙让他今天三更去死
文/潘晓璐我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
开封第一讲书人阅读 160,036评论 0赞 349
道士缉凶录：失踪的卖姜人
文/不坏的土叔我叫张陵，是天一观的道长。经常有香客问我，道长，这世上最难降的妖魔是什么？我笑而不...
开封第一讲书人阅读 57,363评论 1赞 288
港岛之恋（遗憾婚礼）
正文为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
茶点故事阅读 66,460评论 6赞 386
恶毒庶女顶嫁案：这布局不是一般人想出来的
文/花漫我一把揭开白布。她就那样静静地躺着，像睡着了一般。火红的嫁衣衬着肌肤如雪。梳的纹丝不乱的头发上，一...
开封第一讲书人阅读 50,502评论 1赞 292
城市分裂传说
那天，我揣着相机与录音，去河边找鬼。笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。我是一名探鬼主播，决...
沈念sama阅读 39,511评论 3赞 412
双鸳鸯连环套：你想象不到人心有多黑
文/苍兰香墨我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
开封第一讲书人阅读 38,280评论 0赞 270
万荣杀人案实录
序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
沈念sama阅读 44,736评论 1赞 307
护林员之死
正文独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋以下内容为张勋视角年9月15日...
茶点故事阅读 37,014评论 2赞 328
白月光启示录
正文我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
茶点故事阅读 39,190评论 1赞 342
活死人
序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
沈念sama阅读 34,848评论 5赞 338
日本核电站爆炸内幕
正文年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
茶点故事阅读 40,531评论 3赞 322
男人毒药：我在死后第九天来索命
文/蒙蒙一、第九天我趴在偏房一处隐蔽的房顶上张望。院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
开封第一讲书人阅读 31,159评论 0赞 21
一桩弑父案，背后竟有这般阴谋
文/苍兰香墨我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。一阵脚步声响...
开封第一讲书人阅读 32,411评论 1赞 268
情欲美人皮
我被黑心中介骗来泰国打工，没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。一个月前我还...
沈念sama阅读 47,067评论 2赞 365
代替公主和亲
正文我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
茶点故事阅读 44,078评论 2赞 352