계획 기능의 점근 적 시간 복잡성

Question

나는 자신과 내가 가장 고심하고있는 개념을 가르치려고 노력하고있다. 공간과 시간의 복잡성이다. 나는이 장의 끝에 연습 문제를하고 있었고 다음 두 가지를 이해할 수 없었다. 나는 각각의 함수에 대해 점근 적 시간 복잡성 (tight bound)을 계산하려고한다. 이를 위해

;; Finds the largest number below 1000000000 which is divisible by both 3 and 5. 

(define (largest-div-3-or-5) 
    (define (div-3-and-5? n) 
    (and (= (remainder n 3) 0) (= (remainder n 5) 0))) 
    (define (iter n r) 
    (cond ((= n 1000000000) r) 
      ((div-3-and-5? n) (iter (+ n 1) n)) 
      (else (iter (+ n 1) r)))) 
    (iter 1 0)) 

나는 점근 시간 복잡도는 O (n)이 우리가 한 번 매번 정지 조건이 충족되지 않는 한 반복 기능을 호출하기 때문에 생각했다. 이것은 그 (N은 2 ^) O라고 날 같았다

(define (sum-of-cubes-2-different-ways max-n) 
    (define (cube n) (* n n n)) 
    (define (iter n1 n2 n3 n4 results) 
    (cond ((> n1 max-n) results) 
      ((> n2 max-n) (iter (+ n1 1) 1 1 1 results)) 
      ((> n3 max-n) (iter n1 (+ n2 1) 1 1 results)) 
      ((> n4 max-n) (iter n1 n2 (+ n3 1) 1 results)) 
      ; make sure n1,n2 are distinct from n3,n4: 
      ((or (= n1 n3) (= n1 n4) (= n2 n3) (= n2 n4)) 
      (iter n1 n2 n3 (+ n4 1) results)) 
      ((= (+ (cube n1) (cube n2)) (+ (cube n3) (cube n4))) 
      (iter n1 n2 n3 (+ n4 1) (cons (list n1 n2 n3 n4) results))) 
      (else (iter n1 n2 n3 (+ n4 1) results)))) 
    (iter 1 1 1 1 (list))) 

:

번째 함수는 다음과 같이 주어진다. 내가 왜 그렇게 생각 하는지를 설명하기가 어렵 기 때문에 나는 정말로 그것을 눈으로 볼 뿐이다.

Answer 1

목록에서 요소 당 일정한 작업을 수행하기 때문에 첫 번째 시간 복잡도는 O (n)입니다.

두 번째 시간 복잡도는 O (n^4)입니다. 범위 [0, n]에서 선택되는 4 개의 정수의 가능한 모든 조합을 반복합니다. 첫 번째 숫자에는 n 개의 선택 사항이 있고 두 번째 숫자에는 n 개의 선택 사항이 있고 세 번째 숫자에는 n 개의 선택 사항이 있으며 네 번째 숫자에는 n 개의 선택 사항이 있습니다. 따라서 4 개의 숫자로 n^4 개의 가능한 조합이 있으며 조합 당 일정한 수의 작업을 수행하므로 전체적인 복잡성은 O (n^4)입니다.