SICP 연습문제 2.43 친절한 풀이

문제

Louis Reasoner는 연습문제 2.42를 푸는 데 애를 먹고 있다. queens가 돌아가기는 하는 것 같은데, 너무 느려서 참기 힘들다. 또 $6 × 6$문제를 푸는 데 걸리는 시간도 너무 길다고 느낀다. Louis가 Eva Lu Ator에게 도움을 요청하니, Eva는 flatmap 안에서 매핑을 겹쳐 쓸 때 그 차례가 뒤바뀐게 문제라고 한다.

(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))

이렇게 매핑하는 차례가 바귀었다고 해서 프로그램이 느려지는 까닭은 무엇인가? 연습문제 2.42에서 만든 프로그램으로 에잇-퀸 문제를 풀 때 T시간이 걸린다고 하면, Louis가 짠 프로그램으로는 같은 문제를 푸는 데 얼마나 걸리는지 어림잡아 보라.

문제로 부터 얻은 것

map을 겹처서 사용할 때, 그 순서에 따라 프로시저의 시간복잡도가 달라진다는 것을 이해했습니다.
잃어가던 시간복잡도 계산의 감을 찾을 수 있었습니다.

문제풀이

기존의 프로시저와 새로운 프로시저를 비교해 보겠습니다.

;old_one
(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)))
  
;new_one
(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))

a. 시간차이가 나는 이유

두 프로시저 모두 각 열에 하나씩 퀸을 두었을 때, 서로의 체크를 상관하지 않고 퀸을 둘 수 있는 모든 경우의 수를 반환하는 프로시저입니다. 문제에 대해 생각하다보니 "반환하는 결과 값이 같고 각 프로시저의 실행 횟수가 같은데, 어떻게 프로시저의 속도가 다르지?"라는 의문이 들었습니다. 하지만 조금 더 생각해보니, 각 프로시저의 실행 횟수가 달랐습니다. 처음에 만든 프로시저에서는 (queen-cols (- k 1))의 원소마다 enumerate-interval로 new-row값을 붙여 주었습니다. 다른말로 표현하면, 시간의 오래 걸리는 프로시저인 queen-cols를 한번 실행할 동안, 시간이 조금 걸리는 enumerate-interval을 많이 실행한다는 것입니다. 이와는 반대로 Louis의 프로시저는 시간이 조금 걸리는 enumerate-interval을 한번 실행할 동안, 시간이 많이 걸리는 queen-cols를 여러번 실행합니다. 속도의 차이는 여기서 발생하는 것입니다.

b. 시간 차이의 정도

가장 시간이 오래 걸리는 프로시저는 queen-cols이므로, queen-cols의 실행시간 차이를 비교해보면 전페 실행시간의 차이를 어림잡을 수 있습니다. 또 queen-cols의 실행시간은 결국 (queen-cols 0)을 몇번 실행하는 지를 계산하면 알 수 있습니다. (queens 5)를 구한다고 가정해 봅시다.

기존의 프로시저는 (queen-cols 4)를 처음 한번 사용합니다.
Louis의 프로시저는 (queen-cols 4)를 (enumerate-interval 1 board-size)의 원소의 개수인 5번만큼 실행합니다.

기존의 프로시저는 (queen-cols 3)을 (queen-cols 4)에 의해 한번만 사용합니다.
Louis의 프로시저는 (queen-cols 3)을 $5×4$만큼 사용합니다.

기존의 프로시저는 (queen-cols 2)를 한번만 사용합니다.
Louis의 프로시저는 (queen-cols 2)을 $5×4×3$만큼 사용합니다.

$⋮$

기존의 프로시저는 (queen-cols 0)를 한번만 사용합니다.
Louis의 프로시저는 (queen-cols 0)을 $(n-1)!$만큼 사용합니다.

결국 두 프로시저의 시간복잡도는 $(n-1)!$배만큼 차이가 납니다. 기존의 프로시저를 실행하는데 $T$만큼의 시간이 걸렸다면, Louis의 프로시저는 $(n-1)!T$의 시간이 걸립니다.

읽어주셔서 감사합니다.