асимптотическая временная сложность схемных функций - PullRequest
Новая
       29

асимптотическая временная сложность схемных функций

2 голосов
/ 16 февраля 2012

Я пытаюсь научить себя схеме и концепции, с которой я борюсь больше всего, это сложность пространства и времени. Я делал некоторые из упражнений в конце главы, и я не смог понять следующие два. Я пытаюсь выяснить асимптотическую сложность времени (жесткую границу) для каждой из функций. 

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

Мне показалось, что это был О (п ^ 2). Трудно объяснить, почему я так думаю, поэтому я просто смотрю на это по-настоящему.

1 Ответ

1 голос
/ 16 февраля 2012

Первая сложность по времени - O (n), потому что вы выполняете постоянное количество операций для элемента в списке.

Вторая сложность по времени - O (n ^ 4). Вы перебираете все возможные комбинации из 4 целых чисел, выбранных из диапазона [0, n). Существует n вариантов для первого номера, n вариантов для второго номера, n вариантов для третьего номера и n вариантов для четвертого номера. Следовательно, существует n ^ 4 возможных комбинаций четырех чисел, и вы выполняете постоянное количество операций для каждой комбинации, что означает, что общая сложность составляет O (n ^ 4).

...