SICP 問題 2.43
(define (queens board-size) (define (queen-cols k) (if (= k 0) (list empty-board) (filter (lambda (positions) (safe? k positions)) (flatmap (lambda (rest-of-queens) (map (lambda (new-row) (adjoin-position new-row k rest-of-queens)) (enumerate-interval 1 board-size))) (queen-cols (- k 1)))))) (queen-cols board-size)) (define (l-queens board-size) (define (queen-cols k) (if (= k 0) (list empty-board) (filter (lambda (positions) (safe? k positions)) (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))))) (queen-cols board-size))
元のqueensではqueen-colsはboard-size回呼ばれている.
それがLouisのqueensでは(new-row k)一個につき1回呼ばれている.
つまり border-size = xとして
1 + x^1 + x^2 + ... x^(x-1) = (x^x - 1)/ (x - 1)
回呼ばれている.
よってLouisのqueensがかかる時間は T * ((x^x - 1/ (x * (x - 1)))
.