asintotica complessità temporale sistema funzioni

Question

Sto cercando di insegnare a me stesso schema e il concetto sto lottando con il più è lo spazio e la complessità del tempo. Stavo facendo alcuni degli esercizi alla fine del capitolo e non sono stato in grado di capire i due seguenti. Sto cercando di capire un tempo la complessità asintotica (stretto legato) per ciascuna delle funzioni.

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

Per questo ho pensato che il tempo asintotica complessità era O (n) perché stiamo chiamando la funzione iterativa una volta ogni volta che a meno che la condizione di arresto è soddisfatta.

La seconda funzione è data da:

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

Questa mi sembrava che fosse O (n ^ 2). E 'difficile spiegare perché penso che così sto solo eyeballing davvero.

Answer 1

Il primo di una complessità temporale è O (n), perché si sta eseguendo un numero costante di operazioni per ogni elemento della lista.

La seconda di una complessità temporale è O (n ^ 4). Si effettua l'iterazione ogni possibile combinazione di 4 numeri interi raccolti dalla gamma [0, n). Ci sono scelte n per il primo numero, n scelte per il secondo numero, n scelte per il terzo numero, e n scelte per il quarto numero. Pertanto, vi sono n ^ 4 possibili combinazioni dei quattro numeri, e si esegue un numero costante di operazioni per combinazione, che significa che la complessità generale è O (n ^ 4).