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

为此，我认为渐近时间复杂度为 O(n)，因为除非满足停止条件，否则我们每次都调用一次迭代函数。

第二个函数由下式给出：

(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)，因为您要对列表中的每个元素执行恒定数量的操作。

第二个的时间复杂度是 O(n^4)。您正在迭代从范围 [0,n) 中挑选的 4 个整数的所有可能组合。第一个数字有 n 个选项，第二个数字有 n 个选项，第三个数字有 n 个选项，第四个数字有 n 个选项。因此，这四个数字有 n^4 种可能的组合，并且您对每个组合执行恒定数量的操作，这意味着总体复杂度为 O(n^4)。

于 2012-02-16T17:44:45.680 回答