На этом шаге мы поговорим немного о размере задачи и способах его вычисления.
Естественно, первый шаг решения любой вычислительной задачи - понять её. Для его продолжения должны быть чётко определены заданные условия задачи, её входы (исходные данные), выходы (результаты) и отношения между ними. Независимо от типа разрабатываемого алгоритма крайне важно определить размер задачи (или её входной размер). Его следует понимать как математическое выражение, включающее в себя величины, связанные с входными параметрами, которые определяют сложность задачи с точки зрения числа операций, необходимых алгоритму для её решения. При применении рекурсии это особенно важно, так как начальные и рекурсивные условия явно зависят от него.
Во многих задачах размер зависит лишь от одного фактора, коим может оказаться один из входных параметров. Например, размер задач, вычисляющих n-е число Фибоначчи, факториал n или сумму первых n положительных целых чисел, - это и есть входной параметр n. Очевидно, что для таких задач решение меньших её экземпляров (например, для n - 1 или n/2) требует меньшего числа операций. В других случаях размер задачи может не задаваться явно входами, однако синтаксис и конструкции языка программирования позволяют рассчитать её размер. Например, при работе со списками размер задачи часто определяется их длиной, которая может быть получена вызовом функции len().
В других задачах размер может быть выражен как функция входных параметров. Рассмотрим, например, задачу вычисления суммы цифр некоторого положительного целого числа n. Хотя входным параметром является n, размер задачи вовсе не n, а количество цифр n, которое определяет количество выполняемых операций. Формально эта величина может быть выражена как ⌊ lg n ⌋ + 1.
Размер задачи может также зависеть от нескольких входных параметров. Рассмотрим задачу добавления в список элементов подсписка (см. пример 1.6), заданного индексами "lower" и "upper". Решение задачи требует добавления n - m + 1 элементов, где n и m - верхний и нижний индексы соответственно. Таким образом, необходимо произвести n - m добавлений. Небольшая (на единицу) разница между обоими выражениями не имеет значения. Следует отметить, что для решения задачи не нужно знать, сколько именно операций будет выполнено. Напротив, достаточно знать, когда будет достигнуто начальное условие и каким образом сокращать размер задачи, чтобы разложить её на меньшие подзадачи. Для этой последней задачи размер сокращается за счёт уменьшения разности между n и m.
Кроме того, размер задачи не всегда определяет количество выполняемых алгоритмом операций. Рассмотрим задачу сложения элементов квадратной матрицы размером n*n. Поскольку она содержит n2 элементов, для суммирования потребуется n2 - 1 сложений, что является функцией n. Однако в этом случае размер задачи - просто n, а не n2, так как меньшие подзадачи возникают за счёт уменьшения n, а не n2. Если бы матрица была размером n*m, то размер задачи зависел бы от обоих параметров n и m. В частности, размер задачи мог быть nm, и тогда подзадачи меньшего размера можно было получать уменьшением n, m или обоих сразу.
Вообще говоря, размер - это свойство задачи, а не конкретного алгоритма, который её решает. Поэтому это не фактическое количество вычислений, выполненных определённым алгоритмом, так как задачи могут быть решены различными алгоритмами, время выполнения которых может варьироваться в широких пределах. Рассмотрим задачу поиска некоторого числа в сортированном списке из n чисел. В худшем случае (когда такого числа в списке нет и результатом будет False) она может быть решена бездумно за n шагов или более эффективно за ⌊ log2(n) ⌋ + 1 шагов с использованием "двоичного поиска". Но независимо от используемого алгоритма функция, описывающая время его выполнения, зависит только от n. Таким образом, размер задачи - n.
Однако для некоторых задач их размер может быть определён несколькими способами. Более того, выбор размера в процессе рекурсивной разработки влияет на остальную часть решения и в итоге приводит к различным алгоритмам решения задачи. Рассмотрим, например, задачу сложения двух неотрицательных целых чисел a и b с использованием только операций увеличения и уменьшения на единицу. Размер задачи может быть a + b, a, b или min(a, b), при этом конечные алгоритмы будут разными в зависимости от выбранного размера задачи.
На следующем шаге мы рассмотрим начальные условия.
