问题复杂度
我常常低估解决一个问题需要的时间,大致看一眼问题,规划一下思路,然后考虑考虑是否可行,凭感觉给出一个时间。可能对于熟悉的或者解决过的问题,这样子估计的误差不是太大。一旦遇到未知的领域,结果却是谬之千里。当解决未知问题的时候,在纸上勾画出大致的算法是一种情形,一行行代码敲进去的时候,往往会变成另外的情形。大量的细节性的问题没有考虑周全。有时认为困难的地方,反倒是最简单的。那些认为无足轻重的枝枝叶叶,形成一股极大的阻力,缠绕在四肢,降低前进的步伐。周四吧,吃过晚饭之后,突然想写一个程序匹配正则表达式。没有任何外加原因,我自己都奇怪,仿佛上帝说,你写个那样的程序吧。于是我就动手开始了,心想看起来不太难,一个晚上搞定吧。先是写了二百行左右的代码,最后发现整个思路都有问题,第二天又重新开始写,写了又改,改了又写。最后大致剩三四百行。一开始我试图直接从正则表达式构造一个dfa,也就是第一天晚上的想法,后来发现太困难放弃了。又看了看书,也就是那本dragon book。周五一天,完成了从正则表达式到nfa的程序。表面上看使用Thompson构造法似乎很容易就能得到结果了,但我低估了实现数据结构表示形式以及操作等细节实现的复杂度。再加上一大部分调试的时间,磨蹭了一天才完成。昨天跟一个同学出去打台球了,晚上回来看了部电影,没写程序。今天又折腾了一天,主要是将nfa转换成dfa,也就是那个很简单的子集...