read

[CODE]
(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expmod base (/ exp 2) m)
                    m))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m))))
[/CODE]

T(n) = T(n/2) + c 꼴이고 Master theorem 을 적용해보자.

clip_image002

나오므로 수행시간은 clip_image002[5]

[CODE]
(define (expmod-louise base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (* (expmod-louise base (/ exp 2) m)
                       (expmod-louise base (/ exp 2) m))
                    m))
        (else
         (remainder (* base (expmod-louise base (- exp 1) m))
                    m))))
[/CODE]

Louis 가 만든 코드의 프로시져 수행시간을 보자.

T(n) = T(n/2) + T(n/2) + c = 2T(n/2) + c

역시 master theorem 을 적용해보면,

clip_image002[7] 이므로 clip_image002[9] 이 된다.

수행시간 증명이 잘 생각나지 않아 오랜만에 책을 뒤적여 Master theorem 을 봤습니다.

Blog Logo

Ki Sung Bae


Published

Image

Gsong's Blog

Developer + Entrepreneur = Entreveloper

Back to Overview