2

私は自分自身にスキームを教えようとしています、そして私が最も苦労している概念は空間と時間の複雑さです。この章の終わりにいくつかの演習を行っていましたが、次の2つを理解できませんでした。私は、各関数の漸近的な時間計算量（タイトバウンド）を理解しようとしています。

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

このため、停止条件が満たされない限り、反復関数を毎回1回呼び出すため、漸近時間計算量はO（n）であると考えました。

2番目の関数は次のように与えられます。

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

これは私にはO（n ^ 2）のように見えました。なぜそう思うのか説明が難しいので、本当に目が離せません。

4

1 に答える 1

1

リスト内の要素ごとに一定数の操作を実行しているため、最初の時間計算量はO（n）です。

2番目の時間計算量はO（n ^ 4）です。[0、n）の範囲から選択された4つの整数のすべての可能な組み合わせを反復処理しています。最初の番号にはn個の選択肢、2番目の番号にはn個の選択肢、3番目の番号にはn個の選択肢、4番目の番号にはn個の選択肢があります。したがって、4つの数値の可能な組み合わせはn ^ 4あり、組み合わせごとに一定数の操作を実行します。これは、全体的な複雑さがO（n ^ 4）であることを意味します。

于 2012-02-16T17:44:45.680 に答える