问题复杂度

我常常低估解决一个问题需要的时间,大致看一眼问题,规划一下思路,然后考虑考虑是否可行,凭感觉给出一个时间.

可能对于熟悉的或者解决过的问题,这样子估计的误差不是太大.一旦遇到未知的领域,结果却是谬之千里.

当解决未知问题的时候,在纸上勾画出大致的算法是一种情形,一行行代码敲进去的时候,往往会变成另外的情形.大量的细节性的问题没有考虑周全.有时认为困难的地方,反倒是最简单的.那些认为无足轻重的枝枝叶叶,形成一股极大的阻力,缠绕在四肢,降低前进的步伐.

周四吧,吃过晚饭之后,突然想写一个程序匹配正则表达式.没有任何外加原因,我自己都奇怪,仿佛上帝说,你写个那样的程序吧.

于是我就动手开始了,心想看起来不太难,一个晚上搞定吧.

先是写了二百行左右的代码,最后发现整个思路都有问题,第二天又重新开始写,写了又改,改了又写,最后大致剩三四百行.

一开始我试图直接从正则表达式构造一个dfa,也就是第一天晚上的想法,后来发现太困难放弃了.又看了看书,也就是那本dragon book.周五一天,完成了从正则表达式到nfa的程序.表面上看使用Thompson构造法似乎很容易就能得到结果了,但我低估了实现数据结构表示形式以及操作等细节实现的复杂度.再加上一大部分调试的时间,磨蹭了一天才完成.

昨天跟一个同学出去打台球了,晚上回来看了部电影,没写程序.

今天又折腾了一天,主要是将nfa转换成dfa,也就是那个很简单的子集构造算法,描述起来是很简单的,感觉也不复杂.可我慢慢腾腾的花了一天才搞定.九点钟的时候,得到了一个还算满意的结果.

完成的时候,心情挺不错.似乎费心力的那么长的时间不算什么.也许大部分人都是这样子,在完成一件事情之后,忽略掉为完成它而付出的努力.

很多时候,不单是程序,通常生活中也常常低估事情的复杂性,人的力量,凭感觉似乎能做很多事情,其实一段时间之内,真正能做好的,也就那么一两件而已.