Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих - Адитья Бхаргава Страница 44

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" для любых входных значений

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