方案功能的渐近时间复杂性

Question

我想教自己的方案和我最挣扎的概念是空间和时间的复杂性。本章末尾我正在做一些练习，但我还没有弄清楚以下两点。我试图找出每个函数的渐近时间复杂度（严格界限）。

;; 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）。很难解释为什么我这么认为，所以我只是真正地注视它。

Answer 1

第一个人的时间复杂度是O（n），因为你在列表中每个元素执行一个固定数量的操作。

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