Какие константы упоминаются в определении SICP порядка роста? - PullRequest
Новая
       16

Какие константы упоминаются в определении SICP порядка роста?

1 голос
/ 04 мая 2019

В разделе 1.2.3 Структура и интерпретация программ дает это формальное определение порядка роста:

Мы говорим, что R (n) имеет порядок роста Θ (f (n)), записанный R (n) = Θ (f (n)) (произносится как «тета f (n)»), если есть положительные константы k 1 и k 2 не зависит от n, так что k 1 f (n) ≤ R (n) ≤ k 2 f (n) для любого достаточно большого значения n , (Другими словами, для больших n значение R (n) находится между k 1 f (n) и k 2 f (n).)

Какое значение имеют константы k 1 и k 2 ? У меня проблемы с отображением этого формального определения в примерах из реального мира, потому что константы больше не упоминаются.

Может быть, k 1 f (n) ≤ R (n) означает, что наблюдается некоторый наблюдаемый рост? А может быть R (n) ≤ k 2 f (n) означает, что f (n) является верхним пределом роста? Но если R (n) = Θ (f (n)) и k 1 - положительная константа, то когда k 1 f (n) когда-либо будет меньше, чем R (n) ? Кажется, что условие выполняется только тогда, когда k 1 равно 1.

1 Ответ

0 голосов
/ 06 мая 2019

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

Что делает определение Θ особенно запутанным, так это то, что оно не относится к ресурсу, который измеряет R, ни к процессу, использующему ресурс.

Примеры R (n) могут быть:

  • Количество регистров, используемых для суммирования n чисел.
  • Диск, используемый для перекодирования n ГБ видео
  • Время, необходимое для запуска n дронов.

Но в определении Θ не упоминаются ресурсы (регистры, диск, время) и процессы (суммирование, транскодирование или запуск).

Если наш «процесс» представляет собой программную процедуру с именем p, то у нас есть три совершенно разные «функции»: 

p(n) - a procedural function that programmers work with.
R(n) - a measuring function like ones used by engineers.
f(n) – a 'pure' mathematical function.

Если мы используем в качестве примера факториальную процедуру, которая имеет Θ (n) рост по времени, мы получили бы: 

p(n) = (define (factorial n) (if (= n 1) 1 (* n (factorial (- n 1)))))
R(n) = The time in seconds for (factorial n) to complete.
f(n) = n

R (n) = f (n) подразумевает (факториал 17) для запуска ровно 17 секунд, что маловероятно.

Определение Θ (n) гласит, что k₂ и k₂ существуют так, что когда n достаточно велико: 

k₁ * n <= "Time taken for (factorial n) to run in seconds" <= k₂ * n

На современном компьютере k₁ должно быть очень маленьким, чтобы k₁ * n было меньше, чем фактическое время работы.

Для дерево-рекурсивной процедуры Фибоначчи рост равен Θ (1.618ⁿ), поэтому имеем: 

p(n) = (define (fib n) (cond ((= n 0) 0) ((= n 1) 1)  (else ... )))
R(n) = The time in seconds for (fib n) to complete.
f(n) = 1.618ⁿ

и определение гласит, что k₁ и k₂ существуют так, что: 

k₁ * 1.618ⁿ <= "Time taken for (fib n) to run" <= k₂ * 1.618ⁿ)

(я использовал «1.618» для золотого рациона вместо «φ»)

...