О-большое. Оценка скорости алгоритма

Специальная нотация «О-большое» описывает скорость работы алгоритма. Зачем вам это? Время от времени вам предется использовать чужие алгоритмы. Поэтому неплохо было бы понимать, насколько быстро или медленно они работают. В этой статье я объясню, что представляет собой «О-большое», и приведу список самых распространенных вариантов времени выполнения для некоторых алгоритмов.

Время выполнения алгоритмов растет с разной скоростью

«О-большое» описывает, насколько быстро работает алгоритм. предположим, имеется список размером n. Простой поиск должен проверить каждый элемент, поэтому ему придется выполнить n операций. Время выполнения «О-большое» имеет вид О(n). постойте, но где же секунды? А их здесь нет — «О-большое» не сообщает скорость в секундах, а позволяет сравнить количество операций. Оно указывает, насколько быстро возрастает время выполнения алгоритма.:

Как записывается О-большое

Такая запись сообщает количество операций, которые придется выполнить алгоритму. Поэтому, она называется «О-большое», потому что перед количеством операций становится символ «О».

«О-большое» определяет время выполнения в худшем случае

Предположим, вы используете простой поиск для поиска фамилий в телефонной книге. Вы знаете, что простой поиск выполняется за время O(n), то есть в худшем случае вам придется просмотреть каждую без исключения запись в телефонной книге. Но представьте, что искомая фамилия начинается на букву «А» и этот человек стоит на самом первом месте в вашей книге. В общем, вам не пришлось просматривать все записи — вы нашли нужную фамилию с первой попытки. Отработал ли алгоритм за время O(n)? А может, он занял время O(1), потому что результат был получен с первой попытки?

Простой поиск все равно выполняется за время O(n). просто в данном случае вы нашли нужное значение моментально; это лучший возможный случай. Однако «О-большое» описывает худший возможный случай. Фактически вы утверждаете, что в худшем случае придется просмотреть каждую запись в телефонной книге по одному разу. Это и есть время O(n). И это дает определенные гарантии — вы знаете, что простой поиск никогда не будет работать медленнее O(n).

Типичные примеры «О-большого»

Ниже перечислены пять разновидностей «О-большого», которые будут встречаться вам особенно часто, в порядке убывания скорости выполнения.

  1. O(log n), или логарифмическое время. Пример: бинарный поиск.
  2. O(n), или линейное время. Пример: простой поиск.
  3. O(n * log n). Пример: эффективные алгоритмы сортировки (быстрая сортировка)
  4. O(n^2). Пример: медленные алгоритмы сортировки (сортировка выбором)
  5. O(n!). Пример: очень медленные алгоритмы.

Основные результаты:

  1. Скорость алгоритмов изменяерся не в секундах, а в теме роста количества операций.
  2. По сути формула описывает, насколько быстро возрастает время выполнения алгоритма с увеличением размера входных данных.
  3. Время выполнения алгоритмов выражается как «О-большое».
  4. Время выполнения O(log n) быстрее O(n), а с увеличением размера списка, в котором ищется значение, оно становится намного быстрее.

Наглядное представление «О-большое»

Допустим, вы должны построить сетку из 16 квадратов:

Алгоритм 1:

Как вариант можно нарисовать 16 квадратов, по одному за раз. Напоминаю: «О-большое» подсчитывает количество операций. В анном примере рисование квадрата считается одной операцией. Нужно нарисовать 16 квадратов. Сколько операций по рисованию одного квадрата придется выполнить?

Чтобы нарисовать 16 квадратов, потребуется ё6 шагов. Как выглядит время выполнения этого алгоритма?

Алгоритм 2:

А теперь попробуем иначе. Сложите лист пополам.

На этот раз операцией считается сложение листа. Получается, что одна операция создает сразу два прямоугольника!

Сложите бумагу еще раз, а потом еще и еще.

Разверните листок после четырех сложений — получилось замечательная сетка! Каждое сложение удваивает количество прямоугольников. За 4 операции вы создали 16 прямоугольников!

При каждом складывании количество прямоугольников увеличивается вдвое, так что 16 прямоугольников строятся за 4 шага. Как записать время выполнения этого алгоритма? Напишите время выполнения обоих алгоритмов.

Ответы: алгоритм 1 выполняется за время O(n), а алгоритм 2 — за время O(log n).

Упражнения на понимание «О-большое»

Приведите время выполнения «О-большое» для каждого из следующих сценариев.

  1. Известа фамилия, нужно найти номер в телефонной книге.
  2. Известен номер, нужно найти фамилию в телефонной книге. (Подсказка: вам придется провести поиск по всей книге!)
  3. Нужно прочитать телефоны всех людей в телефонной книге.

Ответы:

  1. O(log n)
  2. O(n)
  3. O(n)

Бинарный поиск простыми словами


Deprecated: Function create_function() is deprecated in /home/worldhel/public_html/wp-content/plugins/codecolorer/lib/geshi.php on line 4698

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

Бинарный поиск — это алгоритм, на входе он получает отсортированный список элементов.

Таким образом, если элемент, который вы ищете, присутствует в списке, то бинарный поиск возвращает ту позицию, в которой он был найден.

В противном случае бинарный поиск возвращает null.

Рассмотрим пример того, как работает бинарный поиск. Сыграем в простую игру: я загадал число от 1 до 100.

123….100

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

Предположм, вы начинаете перебирать все варианты подряд:1,2,3,4
Вот как это будет выглядеть.

Бинарный поиск

Это пример простого поиск. При каждой догадке исключается только одно число. Если я загадал число 99, то, чтобы добраться до него, потребуется 99 попыток!!

Бинарный поиск

Существует другой, более эффективный способ. Начнем с 50.

Бинарный поиск

Слишком мало… но вы только что исключили половину чисел! Теперь вы знаете, что все числа 1-50 меньше загаданного. След. попытка: 75.

Бинарный поиск

На этот раз перелет… Но вы снова исключили половину оставшихся чисел!
С бинарным поиском вы каждый раз загадываете число в середине диапозона и исключатете половину оставшихся чисел. Следующим будет число 63 (по середине между 50 и 75)

Бинарный поиск

Так работает бинарный поиск. При бинарном поиске каждый раз исключается половина чисел.

Предположим, вы ищете слово в словаре с 240 000 словами. Как вы думаете, сколько попыток вам понадобится в худшем случае?

Простой поиск:____шагов
Бинарный поиск:____шагов

При простом поиске может потребоваться 240 000 попыток, если искомое слово находится на самом последней позиции в книге.
С каждым шагом бинарного поиска количество слов сокращается вдвое, пока не останется только одно слово.

Бинарный поиск

Давайте напишем реализцию бинарного поиска на Python.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
def binary_search(list, item):
  # В переменных low и high хранятся границы той части списка, в которой выполняется поиск
  low = 0
  high = len(list) - 1

  # Пока эта часть не сократится до одного элемента...
  while low <= high:
    # ... проверяем средний элемент
    mid = (low + high) // 2
    guess = list[mid]
    # Значение найдено
    if guess == item:
      return mid
    # Много
    if guess > item:
      high = mid - 1
    # Мало
    else:
      low = mid + 1

  # Значение не существует
  return None

# ТЕСТИРУЕМ!
my_list = [1, 3, 5, 7, 9]
print(binary_search(my_list, 3)) # => 1
print(binary_search(my_list, -1)) # => None

Упражнения:

  1. Имеется отсортированный список из 128 имен, и вы ищите в нем значение методом бинарного поиска. Какое максимальное количество проверок для этого может потребоваться?
  2. Предположим, размер списка увеличился вдвое (256 имен). Как изменится максимальное количество проверок?

Ответы:

  1. 7
  2. 8