Владстон Феррейра Фило - Теоретический минимум по Computer Science [Все что нужно программисту и разработчику]

Мы увидели, как можно выражать временную сложность с помощью нотации «О большое» ( O ). На протяжении всей книги мы будем использовать ее, выполняя простой анализ временной сложности алгоритмов. Во многих случаях нет необходимости вычислять T( n ), чтобы определить сложность алгоритма по «O большому». В следующей главе мы увидим более простые способы расчета сложности.

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

• Насколько отличаются алгоритмы по числу требуемых для их выполнения операций?

• Как меняется время, необходимое алгоритму, при умножении объема входных данных на некую константу?

• Будет ли алгоритм по-прежнему выполнять приемлемое количество операций в случае, если вырастет объем входных данных?

• Если алгоритм выполняется слишком медленно для входных данных определенного объема, поможет ли его оптимизация или использование суперкомпьютера?

В следующей главе мы сосредоточимся на том, как связаны стратегии, лежащие в основе дизайна алгоритмов, с их временной сложностью.

• Кнут Д. Искусство программирования. Т. 1 (The Art of Computer Programming, см. https://code.energy/knuth).

• Зоопарк вычислительной сложности (The Computational Complexity Zoo, hackerdashery, см. https://code.energy/pnp).

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

как справляться с повторяющимися задачами посредством итераций ;

как изящно выполнять итерации при помощи рекурсии ;

как использовать полный перебор ;

как выполнять проверку неподходящих вариантов и возвращаться на шаг назад ;

как экономить время при помощи эвристических алгоритмов, помогающих найти разумный выход;

как применять принцип «Разделяй и властвуй» к самым неподатливыми противникам;

как динамически идентифицировать уже решенные задачи, чтобы снова не тратить на них энергию;

как ограничивать рамки задачи.

Вам предстоит познакомиться с множеством инструментов, но не переживайте — мы начнем с простых задач, а затем по мере изучения новых методов постепенно будем находить все лучшие решения. Достаточно скоро вы научитесь просто и изящно справляться с вычислительными задачами.

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

Объединение списков рыб У вас есть списки морских и пресноводных рыб, оба упорядочены в алфавитном порядке. Как создать из них один общий список, тоже отсортированный по алфавиту?

Мы можем сравнивать в цикле верхние элементы двух списков (рис. 3.1).

Данный процесс можно записать в виде одного цикла с условием продолжения while loop:

function merge(sea, fresh)

····result ← List.new

····while not (sea.empty and fresh.empty)

········if sea.top_item > fresh.top_item

············fish ← sea.remove_top_item

·······else

···········fish ← fresh.remove_top_item

·····result.append(fish)

return result

Рис. 3.1.Объединение двух отсортированных списков в третий, тоже отсортированный

Он выполняет обход всех названий рыб из входных списков, совершая фиксированное число операций для каждого элемента [28] Объем входных данных (так называемый размер входа) — это число элементов в обоих входных списках, взятых вместе. Цикл while выполняет три операции для каждого из этих элементов, следовательно, T( n ) = 3 n . . Следовательно, алгоритм слияния merge имеет сложность O ( n ).