Грокаем алгоритмы

А теперь попробуем оценить происходящее с точки зрения теории вычислений и посмотрим, сколько времени будут занимать операции. Напомним, что время O(n) означает, что вы по одному разу обращаетесь к каждому элементу списка. Например, при простом поиске по списку исполнителей каждый исполнитель будет проверен один раз.

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

к вы уже видели, это делается за время 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. Рекурсия