대수 시간 체계 알고리즘

현재 Hailperin, Kaiser 및 Knight의 Scheme "Concrete Abstractions"책을 통해 작업하고 있습니다. 아래에 표시된 동일한 알고리즘의 반복적 인 버전과 반복적 인 버전을 작성했습니다. 이 알고리즘은 수량 또는 일 n 번 작업을 수행하는 데 사용됩니다. 그래서, 일반적으로 함께 - 사본 - of (operation n thing). 예를 들어, 나는 (3 * 3) 또는 (3 * 2)의 3 제곱을 같이 3 등분하여 찾을 수 있습니다.대수 시간 체계 알고리즘

재귀 버전 :

(define together-copies-of-linrec 
    (lambda (combine quantity thing) 
    (define together-iter 
     (lambda (combine start thing) 
     (if (= start quantity) 
      thing 
      (combine (together-iter combine (+ start 1) thing) 
        thing)))) 
     (together-iter combine 1 thing)))

반복 버전 :

(define together-copies-of-linit 
    (lambda (combine quantity thing) 
    (define together-iter 
     (lambda (combine start newthing) 
     (if (= start quantity) 
      newthing 
      (together-iter combine (+ start 1) (combine newthing thing))))) 
    (together-iter combine 1 thing)))

지금, 나는이 알고리즘의 대수 시간 버전을 작성해야하지만, 난 정말 어디서부터 시작 해야할지하지 않습니다. 이 경우 로그 타임으로 만들기 위해 인스턴스 당 작업을 줄일 수있는 방법을 알지 못합니다. combine이 ⁰ referentially 투명하게 보장된다고 가정

출처

2014-09-03 SherMM

, 당신은 이진 트리 ¹로 전체 계산을 보면이의 로그 시간 버전을 작성할 수 있습니다. 예를 들어, 이진 트리로 전화 (together-copies-of * 4 3) 상상 (축약 together-copies-oft 등) :

   (t * 4 3) 
        | 
       ----*----- 
      /  \ 
      /   \ 
     (t * 2 3)   (t * 2 3) 
      |     | 
     -----*-    ---*---- 
    /  \   /  \ 
(t * 1 3) (t * 1 3) (t * 1 3) (t * 1 3)

여기서 요점은 당신이 (t * 1 3) 네 시간을 계산 할 필요가 없습니다, 당신은 (t * 2 3)을 계산하는 데 필요가 없다는 것입니다

두번; 당신은 단지 한 번만 계산하면됩니다. 각 행에서 계산을 한 번만 계산하면 행당 O (1) 연산 만 수행하면됩니다. 이진 트리의 행 수가 요소의 수에 로그이므로, 이는 O (log n) 알고리즘의 작동을 의미합니다. 그 구조가 큰 라인의, 그래서 반드시 선형 시간이 소요 :

프로그램 (둘 다) 선형을 만드는거야 그 : 대조적으로

는, 현재의 알고리즘은 다음과 같습니다.

다음의 간단한 프로그램은 이진 트리 아이디어를 구현합니다.

(define together-copies-of-log 
    (lambda (combine quantity thing) 
    (if (= quantity 1) 
     thing 
     (let ((child (together-copies-of-log combine (/ quantity 2) thing))) 
      (combine child child)))))

난 그냥 빨리 개념을 보여주기 위해 쓴 있기 때문에, 몇 가지 결함이 있습니다 quantity는 2의 거듭 제곱이 아닌 경우

이 실패합니다.
꼬리 재귀가 아닙니다.

독자적인 연습 문제입니다. :)

^{몇 명확히 발언 :}

^{0 : 왜 combine이 referentially 투명해야합니까? 그렇지 않은 경우 두 번의 호출을 combine으로 변경하면 실제로 값이 변경 될 수 있으므로 올바른 변환이되지 않습니다.}

^{1 : 3 진 트리 또는 기타 트리가 아닌 2 진 트리가 왜 필요합니까? combine은 정확히 두 개의 인수를 취하기 때문입니다. 서로 다른 기능을위한 버전을 작성했다면, 나무는 같은 아리 티를가집니다.}

출처

2014-09-03 02:37:52 ikdc

대수 시간 체계 알고리즘

답변

관련 문제