The following is a true story. A few years ago, one of
my graduate students had a big problem. His thesis work involved several intricate operations on a large database. He was now working on the final step. “Dr. Shaffer,” he said, “I am running this program and it seems to be taking a long time.” After examining the algorithm we realized that its running time was Ө(n^2), and that it would likely take one to two weeks to complete. Even if we could keep the computer running uninterrupted for that long, he was hoping to complete his thesis and graduate before then. Fortunately, we realized that there was a fairly easy way to convert
the algorithm so that its running time was Ө(n log n). By the next day he had modified the program. It ran in only a few hours, and he finished his thesis on tim... (查看原文)
As an interesting aside, writing a correct binary search algorithm is not easy. Knuth [Knu98] notes that while the first binary search was published in 1946, the first bug-free algorithm was not published until 1962! Bentley (“Writing Correct Programs” in [Ben00]) has found that 90% of the computer professionals he tested could not write a bug-free binary search in two hours. (查看原文)
涅瓦纳
电子工业出版社2002版
0 有用 豆邮 (65535) 2014-01-17 01:09:06
个人页面有电子版和勘误真是业界良心，可是代码还有一些问题