如果有两个算法A1和A2，他们的运行时间分别是O(n^2)和O(n^3)，那么A1和A2哪个更好呢？答案是不确定。其中的原因主要有两点：

• 根据定义，Big Oh notation仅仅给了function f(n)一个upper bound，却并没有说明这个upper bound与f(n)真实的asymptotic behaviour 的接近程度。例如，对于function f(n) = 2n，f(n)=O(n)或者O(n^2)都是正确的，他们都满足定义。但是很明显，O(n)是一个更为接近的upper bound。
• 有时一个算法可能过于复杂，难以分析，例如我们只能证明出A2的upper bound是O(n^3)，但实际却也可以是O(n^2)。根据定义，f(n)=O(n^3)是没有问题的，但是它的实际作用却削弱了很多。

因此，对于上面的例子，我们只能说A1有一个比较好的Big Oh，却不能说A1一定比A2快。如果想让Big Oh notation 与实际的asymptotic behaviour 更为接近，那么就需要同时为worst case 引入lower bound，当upper bound 与lower bound十分接近的时候，实际的asymptotic behaviour 就被限制在了很小的区域内，从而保证了接近程度。这也就是引入Big Omega，以及Big Theta notations的原因。

昨天终于把一篇会议论文submit了，接下来的一段时间该准备Phd confirmation的事情了，然后就是12月份回国。做research差不多有一年的时间，发了2篇文章，这一篇不知道结果会如何？自我感觉问题不大。但是在做research的过程中老是感觉自己做出来的东西很Naive，读完别人的文章，发现了问题，然后找到还算行之有效的解决方法，于是乎写出文章，做完实验，投到会议上，仅此而已。从理论上看似乎并没有多么的高深。应该是自己的道行还太浅，积累不够，功底太差，思考没有穿透力。似乎有些妄自菲薄，不过还有两年的时间来看自己究竟适不适合做researcher。

iPhone已经签了一个礼拜了，到目前为止，感觉非常不错，至少和我从前用过的PDA HP 4700（已经好久没有动过了...）相比。比较明显的就是浏览网页要比其他的手机或PDA爽很多。iPhone的屏幕没有4700大，分辨率也没有4700高，但是网页浏览体验要强不少，这里不仅仅是网页显示的效果，还包括其他很多的细节。在不大的屏幕上，很多网页不需要横屏就可以看清楚，不需要zoom in。如果把屏幕横过来，绝大部分网页都可以很好的显示。这里不得不佩服apple的设计，牛就是体现在在这种最普通的功能上却有着过人之处。唉，看来我的HP 4700要彻底闲置了。

NameCheap的DNS server挂了，昨天一天域名都ping不通。最终把name server transfer到了media temple，现在一切都OK了。

这是一个逻辑问题，有兴趣的可以看一下Daniel的这个A Little Brain Teaser,下面的comments也很有意思。

最近车坏了，水箱裂了个小缝。运气还不错，车正好在开入车库的一刹那开始冒烟，没有坏在半路上。换了个水箱，花了450刀，就当破财免灾吧。