Exercise 2.43
Louis Reasoner is having a terrible time doing Exercise 2.42. His queens procedure seems to work, but it runs extremely slowly. (Louis never does manage to wait long enough for it to solve even the 6 × 6 case.) When Louis asks Eva Lu Ator for help, she points out that he has interchanged the order of the nested mappings in the flatmap, writing it as
(flatmap
(lambda (new-row)
(map (lambda (rest-of-queens)
(adjoin-position new-row k rest-of-queens))
(queen-cols (- k 1))))
(enumerate-interval 1 board-size))
Explain why this interchange makes the program run slowly. Estimate how long it will take Louis’s program to solve theeight-queens puzzle, assuming that the program in Exercise 2.42 solves the puzzle in time T.
标签：2.42,2.43,Louis,每日,sicp,program,board,queens,size From： https://www.cnblogs.com/think2times/p/18461838慢的原因比较好理解，Louis 的答案每一次都要把 queen-cols 计算
(enumerate-interval 1 board-size)遍，一共算了 board-size^board-size 遍，对于八皇后问题就是 8^8 遍；对于练习 2.42 的原方法，每次循环都会减一次，所以一共计算了 n! 次，如果原方法时间为 T，那么 Louis 的方法要用的时间是 8^8/8!*T.