Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих

Глава 1

1.1 Имеется отсортированный список из 128 имен, и вы ищете в нем значение методом бинарного поиска. Какое максимальное количество проверок для этого может потребоваться?

Ответ: 7

1.2 Предположим, размер списка увеличился вдвое. Как изменится максимальное количество проверок?

Ответ: 8

1.3 Известна фамилия, нужно найти номер в телефонной книге.

Ответ: O(log n)

1.4 Известен номер, нужно найти фамилию в телефонной книге. (Подсказка: вам придется провести поиск по всей книге!)

Ответ: O(n).

1.5 Нужно прочитать номера всех людей в телефонной книге.

Ответ: O(n).

1.6 Нужно прочитать телефоны всех людей, фамилии которых начинаются с буквы «А». (Вопрос с подвохом! В нем задействованы концепции, которые более подробно рассматриваются в главе 4. Прочитайте ответ — скорее всего, он вас удивит!)

Ответ: O(n). Возможно, кто-то подумает: «Я делаю это только для одной из 26 букв, а значит, время выполнения должно быть равно O(n/26).» Запомните простое правило: в «O-большое» игнорируются числа, задействованные в операциях сложения, вычитания, умножения или деления. Ни одно из следующих значений не является правильной записью «O-большое»: O(n + 26), O(n – 26), O(n * 26), O(n / 26). Все они эквивалентны O(n)! Почему? Если вам интересно, найдите раздел «Снова об “O-большом”» в главе 4 и прочитайте о константах в этой записи (константа — это просто число; в этом вопросе 26 является константой).

Глава 2

2.1 Допустим, вы строите приложение для управления финансами.

Ежедневно вы записываете все свои траты. В конце месяца вы анализируете расходы и вычисляете, сколько денег было потрачено. При работе с данными выполняется множество операций вставки и относительно немного операций чтения. Какую структуру использовать — массив или список?

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

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

Какую структуру данных вы бы использовали для реализации этой очереди — массив или связанный список? (Подсказка: связанные списки хорошо подходят для вставки/удаления, а массивы — для произвольного доступа к элементам. Что из этого понадобится в данном случае?)

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

2.3 Проведем мысленный эксперимент. Допустим, Facebook хранит список имен пользователей. Когда кто-то пытается зайти на сайт Facebook, система пытается найти имя пользователя. Если имя входит в список имен зарегистрированных пользователей, то вход разрешается. Пользователи приходят на Facebook достаточно часто, поэтому поиск по списку имен пользователей будет выполняться часто. Будем считать, что Facebook использует бинарный поиск для поиска в списке. Бинарному поиску необходим произвольный доступ — алгоритм должен мгновенно обратиться к среднему элементу текущей части списка. Зная это обстоятельство, как бы вы реализовали список пользователей — в виде массива или связанного списка?

Ответ: В виде отсортированного массива. Массивы обеспечивают произвольный доступ — вы можете мгновенно получить элемент из середины массива. Со связанными списками это невозможно. Чтобы получить элемент из середины связанного списка, вам придется начать с первого элемента и переходить по ссылкам до нужного элемента.

2.4 Пользователи также довольно часто создают новые учетные записи на Facebook. Предположим, вы решили использовать массив для хранения списка пользователей. Какими недостатками обладает массив для выполнения вставки? Допустим, вы используете бинарный поиск для нахождения учетных данных. Что произойдет при добавлении новых пользователей в массив?

Ответ: Вставка в массив выполняется медленно. Кроме того, если вы используете бинарный поиск для нахождения имен пользователей, массив необходимо отсортировать. Предположим, пользователь по имени Adit B регистрируется на Facebook. Его имя будет вставлено в конец массива. Следовательно, массив нужно будет сортировать при каждой вставке нового имени!

2.5 В действительности Facebook не использует ни массив, ни связанный список для хранения информации о пользователях. Рассмотрим гибридную структуру данных: массив связанных списков. Имеется массив из 26 элементов. Каждый элемент содержит ссылку на связанный список. Например, первый элемент массива указывает на связанный список всех имен пользователей, начинающихся на букву «A». Второй элемент указывает на связанный список всех имен пользователей, начинающихся на букву «B», и т.д.

Предположим, пользователь с именем «Adit B» регистрируется в Facebook и вы хотите добавить его в список. Вы обращаетесь к элементу 1 массива, находите связанный список элемента 1 и добавляете «Adit B» в конец списка. Теперь предположим, что зарегистрировать нужно пользователя «Zakhir H». Вы обращаетесь к элементу 26, который содержит связанный список всех имен, начинающихся с «Z», и проверяете, присутствует ли «Zakhir H» в этом списке.

Теперь сравните эту гибридную структуру данных с массивами и связанными списками. Будет она быстрее или медленнее каждой исходной структуры при поиске и вставке? Приводить время выполнения «O-большое» не нужно, просто выберите одно из двух: быстрее или медленнее.

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

Что же в действительности использует сервис Facebook? Вероятно, десяток разных баз данных, за которыми стоят разные структуры данных: хеш-таблицы, в-деревья и т.д. Массивы и связанные списки становятся структурными элементами для построения более сложных структур данных.

Глава 3

3.1 Предположим, имеется стек вызовов следующего вида:

Что можно сказать о текущем состоянии программы на основании этого стека вызовов?

Ответ: Некоторые наблюдения, о которых вы могли бы упомянуть:

• сначала вызывается функция greet для переменной name= maggie;

• затем функция greet вызывает функцию greet2 для переменной name = maggie;

• на этой стадии функция greet находится в незавершенном, приостановленном состоянии;

• текущим вызовом функции является вызов greet2;

• после завершения этого вызова функция greet продолжит выполнение.

3.2 Предположим, вы случайно написали рекурсивную функцию, которая бесконечно вызывает саму себя. Как вы уже видели, компьютер выделяет память в стеке при каждом вызове функции. А что произойдет со стеком при бесконечном выполнении рекурсии?

Ответ: Стек будет расти бесконечно. Каждой программе выделяется ограниченный объем памяти в стеке. Когда все пространство будет исчерпано (а рано или поздно это произойдет), программа завершится с ошибкой переполнения стека.

Глава 4

4.1 Напишите код для функции sum (см. выше).

Ответ:

def sum(list):

if list == []:

return 0

return list[0] + sum(list[1:])

4.2 Напишите рекурсивную функцию для подсчета элементов в списке.

Ответ:

def count(list):

if list == []:

return 0

return 1 + count(list[1:])

4.3 Найдите наибольшее число в списке.

Ответ:

def max(list):

if len(list) == 2:

return list[0] if list[0] > list[1] else list[1]

sub_max = max(list[1:])

return list[0] if list[0] > sub_max else sub_max

4.4 Помните бинарный поиск из главы 1? Он тоже относится к классу алгоритмов «разделяй и властвуй». Сможете ли вы определить базовый и рекурсивный случай для бинарного поиска?

Ответ: Базовым случаем для бинарного поиска является массив, содержащий всего один элемент. Если искомый элемент совпадает с элементом массива – вы нашли его! В противном случае элемент в массиве отсутствует.

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

Запишите «O-большое» для каждой из следующих операций.

4.5 Вывод значения каждого элемента массива.

Ответ: O(n).

4.6 Удвоение значения каждого элемента массива.

Ответ: O(n).

4.7 Удвоение значения только первого элемента массива.

Ответ: O(1).

4.8 Создание таблицы умножения для всех элементов массива. Например, если массив состоит из элементов [2, 3, 7, 8, 10], сначала каждый элемент умножается на 2, затем каждый элемент умножается на 3, затем на 7 и т.д.

Ответ: O(n2).

Глава 5

Какие из следующих функций являются последовательными?

5.1 f(x) = 1 Возвращает "1" для любых входных значений

Ответ: Функция последовательна.

5.2 f(x) = rand() Возвращает случайное число

Ответ: Функция непоследовательна.

5.3 f(x) = next_empty_slot() Возвращает индекс следующего пустого элемента в хеш-таблице

Ответ: Функция непоследовательна.

5.4 f(x) = len(x) Возвращает длину полученной строки

Ответ: Функция последовательна.

Предположим, имеются четыре хеш-функции, которые получают строки.

1. Первая функция возвращает «1» для любого входного значения.

2. Вторая функция возвращает длину строки в качестве индекса.

3. Третья функция возвращает первый символ строки в качестве индекса. Таким образом, все строки, начинающиеся с «a», хешируются в одну позицию, все строки, начинающиеся с «b», — в другую и т.д.

4. Четвертая функция ставит в соответствие каждой букве простое число: a = 2, b = 3, c = 5, d = 7, e = 11 и т.д. Для строки хеш-функцией становится остаток от деления суммы всех значений на размер хеша. Например, если размер хеша равен 10, то для строки «bag» будет вычислен индекс 3 + 2 + 17 % 10 = 22 % 10 = 2.

В каком из этих примеров хеш-функции будут обеспечивать хорошее распределение? Считайте, что хеш-таблица содержит 10 элементов.

5.5 Телефонная книга, в которой ключами являются имена, а значениями — номера телефонов. Задан следующий список имен: Esther, Ben, Bob, Dan.

Ответ: Хеш-функции С и D обеспечивают хорошее распределение.

5.6 Связь размера батарейки с напряжением. Размеры батареек: A, AA, AAA, AAAA.

Ответ: Хеш-функции B и D обеспечивают хорошее распределение.

5.7 Связь названий книг с именами авторов. Названия книг: «Maus», «Fun Home», «Watchmen».

Ответ: Хеш-функции B, С и D обеспечивают хорошее распределение.

Глава 6

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

6.1 Найдите длину кратчайшего пути от начального до конечного узла.

Ответ: Длина кратчайшего пути равна 2.

6.2 Найдите длину кратчайшего пути от «cab» к «bat».

Ответ: Длина кратчайшего пути равна 2.

6.3 Перед вами небольшой граф моего утреннего распорядка.

Для каждого из следующих трех списков укажите, действителен он или недействителен.

Ответы: A — недействителен; B — действителен; С — недействителен.

6.4 Немного увеличим исходный граф. Постройте действительный список для этого графа.

Ответ: 1 — Проснуться; 2 — Сделать зарядку; 3 — Принять душ; 4 — Почистить зубы; 5 — Одеться; 6 — Упаковать обед; 7 — Позавтракать.

6.5 Какие из следующих графов также являются деревьями?

Ответы: A — дерево; B — не дерево; C — дерево. В последнем примере дерево просто повернуто набок. Деревья составляют подкатегорию графов, поэтому любое дерево является графом, но граф не обязательно является деревом.

Глава 7

7.1 Каков вес кратчайшего пути от начала до конца в каждом из следующих графов?

Ответы: A — 8; B — 60; C — каверзный вопрос (кратчайший путь не существует из-за наличия цикла с отрицательным весом).

Глава 8

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

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

8.2 Вы едете в Европу, и у вас есть 7 дней на знакомство с достопримечательностями. Вы присваиваете каждой достопримечательности стоимость в баллах (насколько вы хотите ее увидеть) и оцениваете продолжительность поездки. Как обеспечить максимальную стоимость (увидеть все самое важное) во время поездки? Предложите жадную стратегию. Будет ли полученное решение оптимальным?

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

Для каждого из приведенных ниже алгоритмов укажите, является ли этот алгоритм жадным или нет.

8.3 Быстрая сортировка.

Ответ: Нет.

8.4 Поиск в ширину.

Ответ: Да.

8.5 Алгоритм Дейкстры.

Ответ: Да.

8.6 Почтальон должен доставить письма в 20 домов. Ему нужно найти кратчайший путь, проходящий через все 20 домов. Является ли эта задача NP-полной?

Ответ: Да.

8.7 Имеется задача поиска максимальной клики в множестве людей (кликой называется множество людей, каждый из которых знаком со всеми остальными.) Является ли эта задача NP-полной?

Ответ: Да.

8.8 Вы рисуете карту США, на которой два соседних штата не могут быть окрашены в одинаковый цвет. Требуется найти минимальное количество цветов, при котором любые два соседних штата будут окрашены в разные цвета. Является ли эта задача NP-полной?

Ответ: Да.

Глава 9

9.1 Предположим, к предметам добавился еще один: MP3-плеер. Он весит 1 фунт и стоит $1000. Стоит ли брать его?

Ответ: Да. Вы сможете положить в рюкзак MP3-плеер, iPhone и гитару общей стоимостью $4500.

9.2 Предположим, что вы собираетесь в турпоход. Емкость вашего рюкзака составляет 6 фунтов, и вы можете взять предметы из следующего списка. У каждого предмета имеется стоимость; чем она выше, тем важнее предмет:

• Вода, 3 фунта, 10

• Книга, 1 фунт, 3

• Еда, 2 фунта, 9

• Куртка, 2 фунта, 5

• Камера, 1 фунт, 6

Как выглядит оптимальный набор предметов для похода?

Ответ: Возьмите воду, еду и камеру.

9.3 Нарисуйте и заполните таблицу для вычисления самой длинной общей подстроки между строками blue и clues.

Ответ:

Глава 10

10.1 В примере с Netflix сходство между двумя пользователями оценивалось по формуле расстояния. Но не все пользователи оценивают фильмы одинаково. Допустим, есть два пользователя, Йоги и Пинки, вкусы которых совпадают. Но Йоги ставит 5 баллов любому фильму, который ему понравился, а Пинки более разборчива и ставит «пятерки» только самым лучшим фильмам. Вроде бы вкусы одинаковые, но по метрике расстояния они не являются соседями. Как учесть различия в стратегиях выставления оценок?

Ответ: Можно воспользоваться нормализацией: вы вычисляете среднюю оценку для каждого человека и используете ее для масштабирования оценок. Например, вы определили, что средняя оценка Пинки равна 3, а средняя оценка Йоги – 3,5. Соответственно оценки Пинки немного увеличиваются так, чтобы ее средняя оценка тоже была равна 3,5. После этого оценки можно сравнивать по единой шкале.

10.2 Предположим, Netflix определяет группу «авторитетов». Скажем, Квентин Тарантино и Уэс Андерсон относятся к числу авторитетов Netflix, поэтому их оценки оказывают более сильное влияние, чем оценки рядовых пользователей. Как изменить систему рекомендаций, чтобы она учитывала повышенную ценность оценок авторитетов?

Ответ: При применении алгоритма k ближайших соседей можно увеличить вес оценок авторитетов. Предположим, у вас трое соседей: Джо, Дэйв и Уэс Андерсон (авторитет.) Они поставили фильму «Гольф-клуб» оценки 3, 4 и 5 соответственно. Вместо того чтобы вычислять среднее арифметическое их оценок (3 + 4 + 5 / 3 = 4 звезды), вы просто повышаете вес оценки Уэса Андерсона: 3 + 4 + 5 + 5 + 5 / 5 = 4,4 звезды.

10.3 У сервиса Netflix миллионы пользователей. В приведенном ранее примере рекомендательная система строилась для пяти ближайших соседей. Пять — это слишком мало? Слишком много?

Ответ: Слишком мало. Если ограничиться малым числом соседей, существует высокая вероятность того, что результаты будут искажены. Существует хорошее эмпирическое правило: для N пользователей следует рассматривать sqrt(N) соседей.