Skip to main content

Asymptotic Notation

One of my reading projects is to work on the Introduction to Algorithm.

After a few chapters I realized that I might have already forgot all little pieces of mathematics learned in college.

This note shall keep me aware of the asymptotic notations frequently used in the algorithms:

\(f(n)=\Theta(g(n)) \Leftrightarrow c_{1}g(n) \le f(n) \le c_{2}g(n)\)

\(f(n)=O(g(n)) \Leftrightarrow 0 \le f(n) \le cg(n)\)

\(f(n)=\Omega(g(n)) \Leftrightarrow 0 \le cg(n) \le f(n)\)

\(f(n)=o(g(n)) \Leftrightarrow \lim \limits_{n \to \infty} \frac{f(n)}{g(n)}=0\)

\(f(n)=\omega(g(n)) \Leftrightarrow \lim \limits_{n \to \infty}\frac{f(n)}{g(n)}=\infty\)

To make the notations easier to remember/understand, the book gives the following loose analogies:

\(f(n)=\Theta(g(n)) \approx f(n) = g(n)\)

\(f(n)=O(g(n)) \approx f(n) \le g(n)\)

\(f(n)=\Omega(g(n)) \approx f(n) \ge g(n)\)

\(f(n)=o(g(n)) \approx f(n) < g(n)\)

\(f(n)=\omega(g(n)) \approx f(n) > g(n)\)

看了《叶问2》

五一最后一天去看了《叶问2》。

作为一部武打片,看不到什么打斗动作的新意,甄子丹的“机关枪拳”在《叶问》里还算效果不错的,不过到了《2》好歹也该有些创新吧,可惜没看到;很多打斗场面的画面剪接也不清晰,我看的可是正二八经的宽银幕大电影,却没办法看出谁打谁,怎么打的。只有几块肉晃来晃去……

于是在影院的时候就可以分神想些其他的东西:

类似《叶问》的电影在国人消费群中颇有市场,是不是可以理解为我们的自信心到了空前低落的程度:只能靠“哼哼哈兮”的场面来打鸡血才能看到作为中国人的骄傲和自豪?

如果到了只有中国功夫(且不论电影里的是不是真的功夫)才能让国人抬起头的地步,我们还有必要借助功夫片这种春药来意淫中华的崛起吗?

我猜想影片的本意应该是要宣扬叶问在最后说的人性平等相互尊重,不过我也在猜想多数受众的印象大概只是“叶问的功夫很厉害,所以最后打赢了”。以德服人,现在真的变成笑话了。

中国人的血液被注入了太多的暴力因素,无论言语上还是动作上心理上。身边的诸多事件都能用这个解释。虽然我在这里写这句话,但是不能否认自己在看到激烈的打斗时,四肢也会有难以控制的激动,感觉自己就是里面的主角,痛打仇敌很过瘾。从小看武打片的后遗症。

我想今天的电影票买得不是很值。

http://farm5.static.flickr.com/4009/4581136206_c79b65f379_o.jpg

老二陪逛街经验谈

周末出门,偶尔会碰到老二的老婆出街溜老公。 老二倒似很享受出来放风逛街的过程。

再一次看到老二的时候不禁向他讨教如何把陪逛街变成一件趣事。 于是得到老二经验真传,原来逛街的时候可以:

  • 学习英语。超市或是商店里很多商品都会有英文对照翻译,从中可以学到柴米油盐的英文说法,可以了解喇叭裤紧身衣的西洋名称。一来二去,也算小开眼界。
  • 卡拉OK。身边各式音乐不断,真正逛街买东西的人几乎无暇顾及,不过陪逛的人就可以好好享受了:超市播放的一般都是经典金曲,服饰店里总是可以听到热榜新歌。趁这个时候练习,真正K歌的时候就可以小露一手。
  • 锻炼身体。到了超市第一件要做的事,就是选一辆好的购物车。因为它是你接下来1个小时的健身器材。它是双杠又是滑轮车,加上超市劲爆的音乐和复杂的路况,绝对让你下次还想来。
  • 以此类推,娱乐之余别忘了和夫人聊天,不然下次她就不带你出来玩了。

嗯,这个周末我也实践一把……

史上最强的臭豆腐广告语

@中国上海张江地铁站

臭豆腐摊

一句不显眼但是很强悍的广告词:

Smell Smelly, taste tasty

看到后不得不佩服,短短4个词,已经远远超出了原句“闻着臭,吃着香”的意境:

smell和taste是整句的一对核心,闻和吃是品尝臭豆腐的两个步骤;

smell和taste变成smelly和tasty后截然相反的含义刚好用来形容香臭结合的豆腐;

smell->smelly和taste->tasty是系动词变化后成为形容词的仅有两个例子,突出豆腐的独特;

smelly和tasty的韵脚一致,是广告词朗朗上口,口口相传的必备条件

……

只能说,人才啊……

摊前生意太好,总是一堆人,于是借用一下这里的照片……

09总结

那日和朋友聊到最近的改变,他说,好好加油吧,我就等着看你的年度总结了。

有点吓到我:原来还有人预订总结的。好吧,过了09就总。

将至元旦,MSN的更新提示不断的弹出大家的总结日志。

看来09是个大家都要记录的年份。09一定要结。

今天解决完09最后一桩事,在事实上进入了2010。

嗯,可以总结了。

7注定是和我很有一腿的数字,而这是我滑出母体第27年。也许正因如此,09也较过去多些可以记录的东西。

悲情的2008被迫“跳槽”后,原地满血复活般重注热情,投身新革命。

培训了一年,却因为这个或那个原因,没能真正为公司写一行代码:这是程序员的耻辱。

或可庆幸的是,这也许是09的唯一缺憾。

得益于公司的闲适日子,我得余力以思考诸如人生和快乐等抽象命题。花了些时间,虽然没有完全参透怎样的人生方才算是快乐的,但也或有收获:

  • 开始重新看书。有想法是不够的,付诸行动才是王道。在感叹“好久没读书了”那么多年后,09年终于可以开始继续读书学习。感觉很好,很开心。
  • 决定换掉工作。经济环境并非大好,公司老板待我不错。不过报道上网喝茶等下班拿工资的好日子还轮不到我来过,欠了好几年,要学要练的东西太多太多。
  • 过好工作以外的生活。五一的时候洗脸刷牙顺带树立了“要活得像一块大豆腐”的崇高理想,很是兴奋了一把。努力工作之余,休息是需要保证的,娱乐是必不可少的,家务活动能帮就帮,业余爱好也要培养和保护。即便不能活得精彩,但也别留太多遗憾。

一年回了家两趟,表弟有了女儿我们也顺带升了级,父母长辈的衰老已经看得出来,奶奶病痛不断而姥姥却已经只能躺在床上而且辨认不出我来……

我想与时间同行者是很难体会被时间抛下的人的感受的。哪怕亲见,恐怕也只是同情或是感伤。但无论如何,多陪陪他们吧。

婚姻学堂读到三年级,感谢陪伴我学习成长的老妻,我们一起递上期末考试成绩

在过去的那个不折腾元年里,从个人到国家到老天爷,没有一个不在勤勤恳恳地折腾。

以往还可以安慰自己“宁向冠希学英文,莫谈国事”,然而现在的冠希们连中文的说法都不给了。

不容遗忘的纪年。在这个即将拥有世界最大局域网的文明国度,我依然无耻地做着安份良民。但求有一日自己能做的,不仅仅是默默地简单悼念

写到这里想想其实还有很多未完成的2009,但既然还未完成,就先压着。毕竟这篇仅是总结,寄希望于未来一、二年后能写进来。

老二上厕所

老二上厕所。

推开门:靠……前面的家伙没有冲水!

转头到隔壁:靠……这个也没冲而且更不堪……

于是还是回到第一间冲干净,继续五谷轮回。

坐在马桶上,老二自言自语:

嗯,凡事不要轻易放弃,否则后面可能有更大的困难

嗯,出来混,总归要还的。

嗯……

一些零碎的记录

A recommendation is always better than a concern.

“If you are 9-5, you have a problem”

“There is no cry of pain without, at its end, an echo of joy”

不怕像虎一样的对手,也不怕猪一样的队友,怕只怕在自己脑门上画个“王”的猪队友……

国人最为可悲之处在于:在属于程序性的领域积极创新谋求突破,在属于创造性的领域原地踏步遵守程序。这样的69最终是毁灭性的。

书非电子版不能读也。

学习可以中断,但是不能终止。

从“如何成为一名程序员”看到的

以上是在读这本书的时候看到的一段。虽说讲的是如何成为一名程序员,但这样一段文字和我这些时间一直在考虑的问题很是有些关系,不知是碰巧还是其他的原因,让我读到上面这些。我想有必要抄译出来,也算是在思考绳索上打个结做记号:

自我的孩子们出生之后,我便尽量安排出晚上的时间和他们一起度过。现在,我摸索出了最合适自己的工作节奏:先是一整个漫长的白天都在工作,然后在办公室或是就近睡觉(从我家到办公室距离很远);接下来的那天我会及早结束工作回家陪孩子玩,一直到他们睡觉。我并不觉得这样的安排很舒服,但这已经是我在家庭和工作间能做到最好的权衡了。

所以,如果你得了传染病,就回家去;如果你忙得想要自杀,就回家去;如果你累得想要杀人,就回家去。

同样的,如果你的同事中有人呈现神经错乱或是一定程度上的精神问题,你也应该劝他/她回家。

如果疲劳让你开始变得不诚实,开始试着隐瞒事实,那么你应该休息一会了。

不要试图用可卡因或是安非他命来提神。

不要滥用咖啡因。

皮婚 - 我的老妻

“三”对中国人来说是个很重要的数字,三年纪念日也是我们婚姻生活的一个里程碑。

用皮来定义结婚三周年,不知道“皮”对西方意味着什么,但我想这次周年没必要再像以往那样咬文嚼字了。

让我觉得可以写也应该写下来的是这一年里我眼中妻子的改变。

妻子开始研修煮妇之道,开始掌管家政大权,没有储蓄习惯的她也和我一起开始斤斤计较每个月是不是该再多存些钱。劳作时的她俨然看不到女孩的稚气,倒是有几分贤妻的样子。

我也开始习惯了回家就洗澡吃饭,习惯了家里一尘不染,习惯了问她东西放在哪里。要感谢的是妻子把我废了,没有她我在家里会迷路。

争吵的次数没有统计过,不过应该是创下新高。而且越细小的事越是能吵。以至最后也吵出了风格,吵出了模式。我猜想不吵架的男女和不生病的人一样是不健康的,相信妻子慢慢摸出了我什么时候会气急败坏,而我也自信她什么时候将要发点女人脾气。相对于隐忍退让者,她是主张大吵一通倾泻出来然后再沟通解决办法的人。

这个纷繁迷乱的城市,随处都有贵族,放眼尽是奢华。最难能可贵的是妻子在这样的环境下仍能和我一起坚守自己理想的阵地。是她告诉我生活的本质,周末一人一碗热腾腾的泡面和我捧着吃;是她指出我的浮躁,点醒我距离目标还有很大差距;是她抚慰我的病痛,扮演妈妈顾我吃虑我穿;是她带给我更多的快乐,或是吃碗拉面或是做个蛋糕,大小节日哪怕周末都值得我们庆祝;也是她给予我家的温暖,离开公司我的条件反射就是回家,那里是我的暖窝我的乐土。

结婚三年,其实真正的婚姻生活才算刚刚开始。

现在对外一律宣称我们是老夫老妻,已经不是简单的调侃:

三年的相对相处相扶,我也收获了我的老妻。

/galleries/2009.anniversary.jpg

老二说成语-人无远虑必有近忧

人无远虑,必有近忧。

字典说:人没有长远的考虑,一定会出现眼前的忧患。

老二说:如果人没有办法去思考长远的计划,一定是一直被一些眼前的鸡毛琐事所扰。