Грокаем алгоритмы. Иллюстрированное пособие для программистов и любопытствующих - страница 13
к вы уже видели, это делается за время O(n). Итак, имеется операция, выполняемая за время O(n), и ее необходимо выполнить n раз:
Уменьшение количества проверяемых элементов
Возникает закономерный вопрос: при каждом выполнении операций количество элементов, которые нужно проверить, сокращается. Со временем все сведется к проверке всего одного элемента. Почему же время выполнения все равно оценивается как O(n2)? Это хороший вопрос, и ответ на него связан с ролью констант в «O-большом». Тема будет более подробно рассмотрена в главе 4, но я кратко объясню суть. Вы правы, вам действительно не нужно каждый раз проверять весь список из n элементов. Сначала проверяются n элементов, потом n – 1, n – 2 … 2, 1. В среднем проверяется список из ½ × n элементов. Его время выполнения составит O(n × ½ × n). Однако константы (такие как ½) в «O-большом» игнорируются (еще раз: за полным обсуждением обращайтесь к главе 4), поэтому мы просто используем O(n × n), или O(n2).
Все это требует времени O(n × n), или O(n2).
Алгоритмы сортировки очень полезны. Например, теперь вы можете отсортировать:
• имена в телефонной книге;
• даты путешествий;
• сообщения электронной почты (от новых к старым).
Алгоритм сортировки выбором легко объясняется, но медленно работает. Быстрая сортировка — эффективный алгоритм сортировки, который выполняется за время O(n log n). Но мы займемся этой темой в следующей главе!
Пример кода
Мы не будем приводить код сортировки музыкального списка, но написанный ниже код делает нечто очень похожее: он выполняет сортировку массива по возрастанию. Напишем функцию для поиска наименьшего элемента массива:
def findSmallest(arr):
smallest = arr[0]
smallest_index = 0
for i in range(1, len(arr)):
if arr[i] < smallest:
smallest = arr[i]
smallest_index = i
return smallest_index
Теперь на основе этой функции можно написать функцию сортировки выбором:
def selectionSort(arr):
newArr = []
for i in range(len(arr)):
smallest = findSmallest(arr)
newArr.append(arr.pop(smallest))
return newArr
print selectionSort([5, 3, 6, 2, 10])
Шпаргалка
• Память компьютера напоминает огромный шкаф с ящиками.
• Если вам потребуется сохранить набор элементов, воспользуйтесь массивом или списком.
• В массиве все элементы хранятся в памяти рядом друг с другом.
• В списке элементы распределяются в произвольных местах памяти, при этом в одном элементе хранится адрес следующего элемента.
• Массивы обеспечивают быстрое чтение.
• Списки обеспечивают быструю вставку и выполнение.
• Все элементы массива должны быть однотипными (только целые числа, только вещественные числа и т.д.).
3. Рекурсия
В этой главе
• Вы узнаете, что такое рекурсия — метод программирования, используемый во многих алгоритмах. Это важная концепция для понимания дальнейших глав книги.
• Вы научитесь разбивать задачи на базовый и рекурсивный случай. В стратегии «разделяй и властвуй» (глава 4) эта простая концепция используется для решения более сложных задач.
Эта глава мне самому очень нравится, потому что в ней рассматривается рекурсия — элегантный метод решения задач. Рекурсия относится к числу моих любимых тем, но вызывает у людей противоречивые чувства. Они либо обожают ее, либо ненавидят, либо ненавидят, пока не полюбят через пару-тройку лет. Лично я отношусь к третьему лагерю. Чтобы вам было проще освоить эту тему, я дам несколько советов:
• Глава содержит множество примеров кода. Самостоятельно выполните этот код и посмотрите, как он работает.
• Мы будем рассматривать рекурсивные функции. Хотя бы один раз возьмите бумагу и карандаш и разберите, как работает рекурсивная функция: «Так, я передаю функции factorial значение 5, потом возвращаю управление и передаю значение 4 функции factorial, которая…» и т.д. Такой разбор поможет вам понять, как работает рекурсивная функция.
В этой главе также приводится большое количество псевдокода. Псевдокод
