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

См. http://wolframalpha.com.

Любезно предоставлено http://xkcd.com.

Чтобы разобраться в алгоритме, выполните его на бумаге с небольшим объемом входящих данных.

(см. раздел «Комбинаторика»).

Читаются такие конструкции следующим образом: «алгоритм сортировки имеет временную сложность o-n-квадрат».

По поводу сложностей большого «О» большинства алгоритмов, которые выполняют типовые задачи, смотрите http://code.energy/bigo.

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

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

Если вам нужно больше узнать о множествах, см. приложение III.

Палиндромы — это слова и фразы, которые читаются одинаково в обе стороны, например «Ада», «топот», «ротатор».

Любезно предоставлено http://geek-and-poke.com.

В интервале n дней имеется n (n + 1)/2 пар дней (см. раздел «Комбинаторика» главы 1).

Подробнее о степенных множествах см. в приложении III.

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

Задача коммивояжера относится к классу NP-полных задач, который мы обсудили в разделе «Экспоненциальное время» (см. главу 2). Пока не удалось найти оптимальное решение, которое было бы лучше экспоненциального алгоритма.

Любезно предоставлено http://xkcd.com.

Это самый первый алгоритм, который вы увидели в главе 3.

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

Мы не можем проигнорировать x , потому что это не константа. Если размер списка n удвоится, то нам потребуется еще один шаг разбиения. Если n увеличится в четыре раза, тогда нужны будут два дополнительных шага разбиения.

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

В таком случае говорят, что задачи имеют перекрывающиеся подзадачи.

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

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

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

Они сопряжены с разрешением доменного имени, созданием сетевого сокета, установлением шифрованного SSL-соединения и многим другим.

Числа с плавающей точкой — это общепринятый способ представления чисел, имеющих десятичный разделитель.

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

Если узел нарушает это правило, многие алгоритмы поиска по дереву не будут работать.

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

Стратегии автоматической балансировки выходят за рамки этой книги. Если вам любопытно, то в Интернете имеются видеоматериалы, которые показывают, как работают эти алгоритмы.