Вступление

При разработке совершенно нового алгоритма необходим очень тщательный анализ его правильности и эффективности .

Меньше всего вам хотелось бы, чтобы ваше решение было неадекватным для проблемы, для решения которой оно было разработано в первую очередь.

В этой статье мы поговорим о следующих предметах:

• Математическая индукция
• Доказательство правильности
• Инварианты цикла
• Анализ эффективности: отношения повторяемости
• Отношения повторения: линейные и нелинейные
• Решение однородных линейных рекуррентных соотношений
• Теорема магистра компьютерных наук
• Пример: динамическое программирование
• Пример: двоичный поиск
• Заключение

ОТКАЗ ОТ ОТВЕТСТВЕННОСТИ : как вы можете видеть из заголовков разделов, это никоим образом не предназначено для прямого применения. Это теория компьютерных наук , предназначенная только для более глубокого понимания определенных областей практического программирования.

Математическая индукция

Математическая индукция (МИ) - важный инструмент для доказательства утверждения, которое доказывает правильность алгоритма. Общая идея MI состоит в том, чтобы доказать, что утверждение верно для любого натурального числа n .

Что это на самом деле означает?

Это означает, что нам нужно пройти 3 шага:

1. Гипотеза индукции : определите правило, которое мы хотим доказать для каждого n , назовем его F(n)
2. База индукции : доказательство того, что правило действительно для начального значения или, скорее, для отправной точки - это часто подтверждается путем решения гипотезы индукции F(n) для n=1 или любого подходящего начального значения.
3. Индукционный шаг: Доказать , что если мы знаем , что F(n) верно, мы можем step на один шаг вперед и предположим , F(n+1) правильно

Если вы выполнили эти шаги, теперь у вас есть возможность зацикливаться! Нет, правда, это дает нам возможность делать что-то вроде этого:

 for (i in range(n)): 
 T[i] = True 

Базовый пример

Проблема :

Если мы определим S(n) как сумму первых n натуральных чисел, например S(3) = 3+2+1 , докажите, что следующая формула может быть применена к любому n :

$$
S (n) = \ frac {(n + 1) * n} {2}
$

Проследим наши шаги:

1. Гипотеза индукции : S(n) определяется формулой выше

2. База индукции : на этом этапе мы должны доказать, что S(1) = 1 :

   $$
   S (1) = \ frac {(1 + 1) * 1} {2} = \ frac {2} {2} = 1
   $

3. Шаг индукции : на этом шаге нам нужно доказать, что если формула применима к S(n) , она также применима к S(n+1) следующим образом:

   $$ S (n + 1) = \ frac {(n + 1 + 1) * (n + 1)} {2} = \ frac {(n + 2) * (n + 1)} {2} $$

Это известно как импликация (a => b), что просто означает, что мы должны доказать b условии, что мы знаем, что a правильно.

$$
S (n + 1) = S (n) + (n + 1) = \ frac {(n + 1) * n} {2} + (n + 1) = \ frac {n ^ 2 + n + 2n +2} {2}
$

$$
= \ frac {n ^ 2 + 3n + 2} {2} = \ frac {(n + 2) * (n + 1)} {2}
$

Обратите внимание, что S(n+1) = S(n) + (n+1) просто означает, что мы рекурсивно вычисляем сумму. Пример с литералами:
S(3) = S(2) + 3= S(1) + 2 + 3 = 1 + 2 + 3 = 6

QED

Доказательство правильности

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

Вы спросите, почему это так? Что ж, в практическом императивном программировании есть такая вещь, которая называется состоянием , это означает, что вывод программы зависит от трех вещей:

1. Его последовательность инструкций

2. Его входные значения

3. его состояние , а точнее все ранее инициализированные переменные, которые могут каким-либо образом изменить выходное значение

Пример состояния программы

 def foo(x): 
 x = y + 1 
 return x 

Если бы я попросил вас дать мне выходное значение этой функции для x=1 , вы, естественно, сказали бы:

Ну, черт возьми, сэр, как бы нам узнать выходное значение, если бы мы не знали это чертовски y значение.

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

Детерминированная - система без случайных факторов

Это открывает совершенно новую историю о парадигмах программирования, которые имеют полностью прозрачное состояние или, другими словами, БЕЗ ПЕРЕМЕННЫХ . Это может показаться безумием, но оно существует и используется нечасто, особенно при функциональном программировании на Haskell .

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

Пример рекурсии

 def factorial(n): 
 if (n==0): 
 return 1 
 else: 
 return n*factorial(n-1) 

Преобразовано в форму повторения:

$$
Факториал (n) = n * Факториал (n-1)
$

Инварианты цикла

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

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

Самый простой способ решения обеих задач (с помощью математической индукции) - это инварианты цикла :

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

Выбор инвариантного цикла

Инвариант цикла может быть настолько сложным и простым, насколько вы хотите. Однако суть в том, что она должна быть построена так, чтобы как можно точнее походить на рассматриваемую проблему.

Например, я всегда могу сказать, что следующее является инвариантом цикла:

$$({Икс} > y)\operatorname{â\hat{}¨}({Икс} < y)\operatorname{â\hat{}¨}({Икс}==y)$$

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

1. Формула верна ДО выполнения цикла
2. Формула верна ВО ВРЕМЯ выполнения цикла, включая все шаги между ними.
3. Формула верна ПОСЛЕ выполнения цикла

Пример:

Давайте посмотрим на следующий код и определим оптимальный инвариант цикла:

 x = 10 
 y = 4 
 z = 0 
 n = 0 
 while(n < x): 
 z = z+y 
 n = n+1 

Логически этот код просто вычисляет значение x * y и сохраняет его в z, это означает, что z = x*y . Еще одно условие, которое, как мы знаем, всегда будет истинным, - это n <= x (подробнее о равенстве в примере). Но действительно ли эти два аспекта применимы только после того, как программа завершила вычисления?

Значение n - это, по сути, количество циклов, которые уже были выполнены, но также это количество раз, когда z было увеличено на y .

Это означает, что и z = n*y и n <= x могут применяться всегда . Осталось только проверить, действительно ли они могут использоваться в качестве инварианта цикла.

Пример петлевой инвариантности - доказательство по индукции

Во-первых, нам нужно доказать, что инвариант цикла истинен, прежде чем входить в цикл (что эквивалентно доказательству и основанию индукции ):

 # <=> - logical equivalency, left and right sides of the equation have the same logical value (True or False) 
 # <= - less or equal (not to be confused with implication, which also looks like a arrow to the left) 
 x = 10 
 y = 4 
 z = 0 
 n = 0 
 # RULE 1: z == n*y 
 # 0 == 0*4 = 0 <=> True 
 # so RULE 1 applies 
 
 # RULE 2: n <= x 
 # 0 <= 10 <=> True 
 # so RULE 2 applies, therefore the invariant is valid before entering the loop 

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

Следовательно, z' = z+y и n' = n+1 . По сути, нам нужно доказать, что если мы знаем, что инвариант истинен для z и n , он также верен для z' и n' :

$$z^{\operatorname{â\ €\ ²}}\operatorname{знак\ равно}z + y z\operatorname{знак\ равно}п\operatorname{â\hat{}-}y п^{\operatorname{â\ €\ ²}}\operatorname{знак\ равно}п + 1\text{Если\ верно\ следующее,\ инвариант\ верен:\ Â}z^{\operatorname{â\ €\ ²}}\operatorname{знак\ равно}п^{\operatorname{â\ €\ ²}}\operatorname{â\hat{}-}y? z^{\operatorname{â\ €\ ²}}\operatorname{знак\ равно}(п + 1)\operatorname{â\hat{}-}y\operatorname{знак\ равно}п\operatorname{â\hat{}-}y + y\operatorname{знак\ равно}z + y$$

В-третьих, нам нужно проверить, верен ли инвариант после последней итерации цикла. Поскольку n является целым числом, и мы знаем, что n-1<x истинно, но n<x ложно, это означает, что n=x (это причина, по которой инвариант должен включать n<=x , а не n<x ).

Следовательно, мы знаем, что z = x*y .

QED

Анализ эффективности: отношения повторяемости

Когда говорят об эффективности алгоритма, первое, что приходит в голову,

• это рекуррентные отношения. Это просто означает, что функция, такая как f(n) , зависит от ее предшествующих и последующих значений, таких как f(n-1) и f(n+1) .

Простейшим примером такой функции может быть последовательность Фибоначчи:

$$
Фибоначчи (n) = Фибоначчи (n-1) + Фибоначчи (n-2)
$

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

При анализе эффективности алгоритма вы будете решать в основном два типа отношений:

1. Линейные однородные рекуррентные соотношения
2. Нелинейные рекуррентные отношения - пример использования основной теоремы

Решение однородных линейных рекуррентных соотношений

Читая заголовок выше, вы можете спросить себя

"Черт возьми, что это за тарабарщина по математике?!?!"

Что ж, сначала давайте посмотрим на общую формулу:

$$F(п)\operatorname{знак\ равно}а_{1}F(п\operatorname{â\hat{}\ ‘}1) + а_{2}F(п\operatorname{â\hat{}\ ‘}2) + … + а_{k}F(п\operatorname{â\hat{}\ ‘}k).$$

Теперь давайте разберем определение на части размером в байты (каламбур):

1. Линейный относится к тому факту, что функциональные элементы F(something) относятся к первой степени
2. Однородность относится к тому факту, что все дуплеты элементов a*F(something) являются однородными, что означает, что константа не может присутствовать ( a*F(something) = const не может произойти)

Эти рекуррентные отношения решаются с помощью следующей замены:

$$
(1) \ \ F (п) = г ^ п
$

• r - удобно выбранное (комплексное) число

Я буду перечислять полезные формулы, чтобы мне было легче ссылаться на них в примере.

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

Уточнение:

• complex числа имеют форму x = a + bi , x - комплексное число, a и b - простые целые числа, а i - константа:
  $
  \ begin {align}
  i = \ sqrt {-1}
  \ end {align}
  $

• как вы можете заметить, i - очень конкретное число, что означает, что на самом деле у него есть цикл :
  $
  \ begin {align}
  я = \ sqrt {-1} \,
  я ^ 2 = -1 \,
  я ^ 3 = -1 * \ sqrt {-1} \,
  я ^ 4 = 1 \,
  я ^ 5 = я,
  \ end {align}
  $

• это означает, что у i есть цикл length = 5

• другие комплексные числа могут быть адаптированы для получения точного цикла, в котором нет двух одинаковых элементов (кроме начального и конечного элементов)

Используя указанную выше замену, получаем характеристический полином :

$$р^{k}\operatorname{â\hat{}\ ‘}а_{1}р^{k\operatorname{â\hat{}\ ‘}1}\operatorname{â\hat{}\ ‘}а_{2}р^{k\operatorname{â\hat{}\ ‘}2}\operatorname{â\hat{}\ ‘}…\operatorname{â\hat{}\ ‘}а_{k}\operatorname{знак\ равно}0$$

Это очень удобное уравнение, где r может иметь k возможных решений (корней). Кроме того, мы можем представить F(n) как линейную комбинацию всех его предшественников (доказательство правильности этой формулы не будет показано ради вашего и моего собственного здравомыслия):

$$F(п)\operatorname{знак\ равно}\operatorname{â\hat{}\ ‘}\limits_{я\operatorname{знак\ равно}1}^{k}c_{я}р_{я}^{п}$$

• ci - неизвестные коэффициенты, которые указывают, какой r имеет наибольшее влияние при вычислении значения F(n)

Кроме того, если значение корня ( r ) встречается более одного раза, мы говорим, что r имеет кратность ( m ) больше 1.

Это немного изменяет предыдущее уравнение:

$$(2)\text{Â}\text{Â}F(п)\operatorname{знак\ равно}\operatorname{â\hat{}\ ‘}\limits_{я\operatorname{знак\ равно}1}^{s}{час}_{я}(п)$$

• hi может содержать ri , которое вычисляется (с учетом множественности) по формуле:

$$(3)\text{Â}\text{Â}{час}{я}(п)\operatorname{знак\ равно}(C{я,0} + C_{я,1}п + C_{я,2}п^{2} + … + C_{я,мя\operatorname{â\hat{}\ ‘}1}п^{м_{я}\operatorname{â\hat{}\ ‘}1})р_{я}^{п}$$

Поздравляем, теперь мы можем решать самые простые рекуррентные уравнения. Давайте проверим!

Теорема магистра компьютерных наук

Помните, я сказал, что вышеупомянутое - это всего лишь повторяющиеся отношения голой кости? Что ж, теперь мы рассмотрим более сложный, но гораздо более полезный тип рекуррентного отношения.

Основная форма этого нового типа рекуррентного отношения:

$$
T (n) = aT (\ frac {n} {b}) + cn ^ k
$

• из которых все константы равны или больше нуля a,b,c,k >= 0 и b =/= 0

Это гораздо более распространенное рекуррентное отношение, поскольку оно воплощает принцип « разделяй и властвуй» (оно вычисляет T(n) , вычисляя гораздо меньшую задачу, такую как T(n/b) ).

Формула, которую мы используем для вычисления T(n) в случае такого рекуррентного соотношения, выглядит следующим образом:

$$Т(п)\operatorname{знак\ равно}\left{ \begin{matrix} {О(п^{ло{грамм}_{б}а})} & {\text{для}а > б^{k}} \ {О(п^{k}ло{грамм}\text{Â}п)} & {\text{для}а\operatorname{знак\ равно}б^{k}} \ {О(п^{k})} & {\text{для}а < б^{k}} \ \end{matrix} \right.$$

Поскольку приведенная выше формула достаточно логична , и поскольку доказательство на самом деле не тривиально, я бы посоветовал вам просто запомнить его как есть ... но если вы все еще хотите увидеть доказательство, прочтите доказательство теоремы 5.1 1-2 в этом документе. статья .

Пример: двоичный поиск

Если у нас есть отсортированный массив A длины n и мы хотим узнать, сколько времени нам потребуется, чтобы найти конкретный элемент, назовем его, например, z Сначала нам нужно взглянуть на код, который мы будем использовать для поиска указанного элемента с помощью двоичного поиска:

 # leftIndex and rightIndex indicate which part of the original array 
 # we are currently examining, the initial function call is find(A,z,1,n) 
 import math 
 def find(A, z, leftIndex, rightIndex): 
 # if our search range is narrowed down to one element, 
 # we just check if it's equal to z, target being the index of the wanted element 
 # A[target]=z 
 if leftIndex == rightIndex: 
 if A[leftIndex] == z: 
 return leftIndex 
 else: 
 return -1 
 else: 
 middlePoint = math.ceil((leftIndex + rightIndex) / 2) 
 print("{} {} {}".format(leftIndex, rightIndex, middlePoint)) 
 # because the array is sorted, we know that if z < X[middlePoint], 
 # we know it has to be to the left of said element, 
 # same goes if z >= X[middlePoint] and we call 
 # find(A, z, leftIndex, middlePoint - 1) 
 # if z == A[middlePoint]: 
 # return middlePoint 
 if z < A[middlePoint]: 
 return find(A, z, leftIndex, middlePoint - 1) 
 else: # z >= A[middlePoint] 
 # leaving the middle point in this call is intentional 
 # because there is no middle point check 
 # except when leftIndex==rightIndex 
 return find(A, z, middlePoint, rightIndex) 
 
 def main(): 
 A = [1, 3, 5, 7, 8, 9, 12, 14, 22] 
 z = 12 
 target = find(A, z, 0, len(A)) 
 print("Target index: {}".format(target)) 
 
 if __name__ == "__main__": 
 main() 

Самая трудоемкая часть этого поиска - это рекурсия, это означает, что мы можем представить время, необходимое алгоритму двоичного поиска для поиска в массиве длины n используя следующее рекуррентное соотношение:

$$
T (n) = T (\ frac {n} {2}) + 1
$

1 представляет постоянную операцию, такую как проверка значения (например, leftIndex == rightIndex , эта константа на самом деле не так важна, учитывая, что она намного меньше, чем T(n) и T(n\b) ).

Из сопоставления основной формулы основной теоремы с формулой двоичного поиска мы знаем:

$$
а = 1, Ь = 2, с = 1, к = 0 \\ $

Используя формулу основной теоремы для T (n), мы получаем, что:

$$
T (n) = O (журнал \ n)
$
Итак, двоичный поиск действительно более эффективен, чем стандартный линейный поиск.

Пример: динамическое программирование против рекурсии

Давайте в последний раз посмотрим на последовательность Фибоначчи (обещаю, в прошлый раз):

$$
Фибоначчи (n) = Фибоначчи (n-1) + Фибоначчи (n-2)
$

Динамическое программирование, как мы знаем из моей последней статьи, имеет временную сложность O(n) потому что оно использует запоминание и генерирует массив линейно , без ретроспективного анализа (он строит массив с нуля).

Теперь давайте докажем, что использование динамического программирования намного эффективнее.

Анализ сложности времени Фибоначчи

Предположим, что T(n) представляет собой время, необходимое для вычисления n-th элемента последовательности Фибоначчи.

Тогда мы знаем, что применима следующая формула:

$$
Т (п) = Т (п-1) + Т (п-2)
$

Во-первых, нам нужно получить неявную форму уравнения ( математический разговор для того, чтобы разбить все на одну сторону, чтобы на другой стороне был только ноль):

$$
Т (п) -Т (п-1) -Т (п-2) = 0
$

Теперь воспользуемся стандартной заменой (формула (1)):

$$
r ^ nr ^ {n-1} -r ^ {n-2} = 0
$

Чтобы еще больше упростить уравнение, давайте разделим обе части с помощью r на степень наименьшей степени, присутствующей в уравнении (в данном случае это n-2 ):

$$р^{п}\operatorname{â\hat{}\ ‘}р^{п\operatorname{â\hat{}\ ‘}1}\operatorname{â\hat{}\ ‘}р^{п\operatorname{â\hat{}\ ‘}2}\operatorname{знак\ равно}0\text{Â}/р^{п\operatorname{â\hat{}\ ‘}2} р^{п\operatorname{â\hat{}\ ‘}(п\operatorname{â\hat{}\ ‘}2)}\operatorname{â\hat{}\ ‘}р^{п\operatorname{â\hat{}\ ‘}1\operatorname{â\hat{}\ ‘}(п\operatorname{â\hat{}\ ‘}2)}\operatorname{â\hat{}\ ‘}р^{п\operatorname{â\hat{}\ ‘}2\operatorname{â\hat{}\ ‘}(п\operatorname{â\hat{}\ ‘}2)}\operatorname{знак\ равно}0 р^{2}\operatorname{â\hat{}\ ‘}р^{1}\operatorname{â\hat{}\ ‘}р^{0}\operatorname{знак\ равно}0 р^{2}\operatorname{â\hat{}\ ‘}р\operatorname{â\hat{}\ ‘}1\operatorname{знак\ равно}0$$

Этот шаг сделан для того, чтобы мы могли свести проблему к квадратному уравнению .

Используя формулу квадратного уравнения, мы получаем следующие возможные значения для r :

$$р_{1}\operatorname{знак\ равно}\frac{1 + \sqrt{5}}{2},р_{1}\operatorname{знак\ равно}\frac{1\operatorname{â\hat{}\ ‘}\sqrt{5}}{2}$$

Теперь, используя формулу (2) , определяем основную формулу для Fibonacci(n) :

$$Т(п)\operatorname{знак\ равно}C_{1}\operatorname{â\hat{}-}р_{1}^{п} + C_{2}\operatorname{â\hat{}-}р_{2}^{п}$$

Поскольку мы знаем, что Fibonacci(0) = 0 и Fibonacci(1) = 1 , поэтому T(0) = 0 и T(1) = 1 (технически T(0) и T(1) могут быть любым постоянным числом операции, необходимые для вычисления их значений, но на самом деле это не так сильно влияет на результат, поэтому для простоты они 0 и 1 , как и Fib(0) и Fib(1) ), мы можем их использовать чтобы решить уравнение выше для C1 и C2 :

$$Т(0)\operatorname{знак\ равно}0\operatorname{знак\ равно}C_{1}\operatorname{â\hat{}-}р_{1}^{0} + C_{2}\operatorname{â\hat{}-}р_{2}^{0}\operatorname{знак\ равно}C_{1} + C_{2}\text{Что\ означает:\ Â}C_{1}\operatorname{знак\ равно}\operatorname{â\hat{}\ ‘}C_{2}$$

Их, используя T(1) :

$$Т(1)\operatorname{знак\ равно}1\operatorname{знак\ равно}C_{1}\operatorname{â\hat{}-}р_{1}^{1} + C_{2}\operatorname{â\hat{}-}р_{2}^{1}\operatorname{знак\ равно}C_{1}\operatorname{â\hat{}-}р_{1} + C_{2}\operatorname{â\hat{}-}р_{2}\text{Потому\ что\ мы\ знаем\ значения\ r1\ и\ r2,\ а\ также\ следующие:\ Â}C_{1}\operatorname{знак\ равно}\operatorname{â\hat{}\ ‘}C_{2}\text{Мы\ можем\ подставить\ их\ в\ основное\ уравнение:\ Â}\text{Â}1\operatorname{знак\ равно}\operatorname{â\hat{}\ ‘}C_{2}\operatorname{â\hat{}-}\frac{1 + \sqrt{5}}{2} + C_{2}\operatorname{â\hat{}-}\frac{1\operatorname{â\hat{}\ ‘}\sqrt{5}}{2}$$

Когда мы решаем приведенное выше уравнение для C2 мы получаем:

$$C_{1}\operatorname{знак\ равно}\operatorname{â\hat{}\ ‘}\frac{1}{\sqrt{5}}\text{Â}C_{2}\operatorname{знак\ равно}\frac{1}{\sqrt{5}}$$

Это означает, что теперь у нас есть окончательное решение рекуррентного отношения:

$$Т(п)\operatorname{знак\ равно}\operatorname{â\hat{}\ ‘}\frac{1}{\sqrt{5}}\operatorname{â\hat{}-}(\frac{1 + \sqrt{5}}{2})^{п} + \frac{1}{\sqrt{5}}\operatorname{â\hat{}-}(\frac{1\operatorname{â\hat{}\ ‘}\sqrt{5}}{2})^{п}$$

Выведение сложности алгоритма из отношения повторяемости

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

Интересный факт:

Вышеупомянутый метод может также использоваться, чтобы найти формулу для вычисления определенного значения для n-th элемента в последовательности Фибоначчи (функции будут представлять значение n-th элемента, а не количество операций, необходимых для их вычисления)

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

Заключение

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

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