ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 03.12.2023
Просмотров: 393
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
СОДЕРЖАНИЕ
Определение порядка сложности нотации «О-большое» вашего кода
279
также увеличится десятикратно. При увеличении размера books с 10 до 100 алго- ритм переходит от значения 1 + 1 + (2
× 10) + 1, или 23 шага, к 1 + 1 + (2 × 100) + 1, или 203 шага. Число 203 равно приблизительно 10
× 23, так что время выполнения возрастает пропорционально росту n.
1 ... 25 26 27 28 29 30 31 32 ... 40
Почему низкие порядки и коэффициенты не важны
Низкие порядки исключаются из подсчета шагов, потому что они становятся менее значимыми с увеличением размера n. Если список books из приведенной функции readingList()
увеличивается с 10 до 10 000 000 000 (10 миллиардов), количество шагов увеличится с 23 до 20 000 000 003. При достаточно больших n эти три до- полнительных шага ни на что не влияют.
При увеличении объема данных большой коэффициент меньшего порядка может игнорироваться по сравнению с высокими порядками. При определенном разме- ре n более высокие порядки всегда будут медленнее низких порядков. Допустим, имеется функция quadraticExample()
с порядком O(n
2
) и она состоит из 3n
2
шагов.
Другая функция linearExample()
с порядком O(n) состоит из 1000n шагов. Не- важно, что коэффициент 1000 больше коэффициента 3; с ростом n квадратичная операция O(n
2
) станет медленнее линейной операции O(n). Реальный код не столь важен, но он может выглядеть примерно так:
def quadraticExample(someData): # n - размер someData for i in someData: # n шагов for j in someData: # n шагов print('Something') # 1 шаг print('Something') # 1 шаг print('Something') # 1 шаг def linearExample(someData): # n - размер someData for i in someData: # n шагов for k in range(1000): # 1 * 1000 шагов print('Something') # (уже подсчитано)
Функция linearExample()
имеет большой коэффициент (1000) по сравнению с коэффициентом (3) функции quadraticExample()
. Если размер входных данных n равен 10, то функция O(n
2
) вроде бы работает быстрее — всего 300 шагов по срав- нению с 10 000 шагами функции O(n).
Но нотация «О-большое» в основном описывает эффективность алгоритма при большом объеме работы. Когда n достигнет размера 334 и выше, функция quadraticExample()
всегда будет медленнее функции linearExample()
. Даже если linearExample()
равна 1000000n шагов, функция quadraticExample()
все равно будет медленнее, когда n достигнет 333 334. В какой-то момент операция O(n
2
) всегда становится медленнее O(n), или низшей операции. Чтобы убедиться в этом,
280
Глава 13.Измерение быстродействия и анализ сложности алгоритмов взгляните на график нотации «О-большое» на рис. 13.3. На графике представлены все основные порядки нотации «О-большое». По оси x представлен размер данных x, а по оси y — время выполнения, необходимое для выполнения операции.
Вр ем я
Данные n²
n log n n
log n
1
Рис. 13.3. График порядков нотации «О-большое»
Как видно из графика, время выполнения более высоких порядков растет быстрее, чем время низких порядков. Хотя низкие порядки могут иметь более высокие ко- эффициенты, из-за которых они изначально показывают большие затраты времени, рано или поздно высокие порядки их обойдут.
Примеры анализа «О-большое»
Определим порядки «О-большое» для некоторых примеров функций. В этих при- мерах будет использоваться параметр books
, который представляет собой список строк с названиями книг.
Функция countBookPoints()
вычисляет оценку на основании количества книг в списке. Большинство книг получает одно очко, а книги определенного автора получают два очка:
def countBookPoints(books): points = 0 # 1 шаг for book in books: # n * шагов в цикле points += 1 # 1 шаг for book in books: # n * шагов в цикле
Определение порядка сложности нотации «О-большое» вашего кода
281
if 'by Al Sweigart' in book: # 1 шаг points += 1 # 1 шаг return points # 1 шаг
Количество шагов достигает 1 + (n
× 1) + (n × 2) + 1, что преобразуется в 3n + 2 после объединения подобных членов. После исключения составляющих низких порядков и коэффициентов мы приходим к O(n), то есть к линейной сложности, независимо от того, сколько раз перебираются книги — один, два или миллиард.
До настоящего момента все примеры, в которых использовался один цикл, имели линейную сложность, но обратите внимание: все эти циклы выполнялись n раз. Как показывает следующий пример, цикл в коде не всегда подразумевает линейную сложность (которая характеризует циклы, перебирающие входные данные).
Функция iLoveBooks()
выводит сообщения «I LOVE BOOKS!!!» и «BOOKS ARE
GREAT!!!» 10 раз:
def iLoveBooks(books):
for i in range(10): # 10 * шагов в цикле print('I LOVE BOOKS!!!') # 1 шаг print('BOOKS ARE GREAT!!!') # 1 шаг
Функция содержит цикл for
, но этот цикл не перебирает список books и выполняет
20 шагов независимо от размера books
. Можно переписать это как 20(1). После исключения коэффициента 20 остается O(1), то есть постоянная сложность. Все логично: функция выполняется за одно и то же время независимо от n (размера списка books).
Затем рассмотрим функцию cheerForFavoriteBook()
, которая ищет любимую книгу в списке books
:
def cheerForFavoriteBook(books, favorite):
for book in books: # n * шагов в цикле print(book) # 1 шаг if book == favorite: # 1 шаг for i in range(100): # 100 * шагов в цикле print('THIS IS A GREAT BOOK!!!') # 1 шаг
Цикл for book перебирает список books
, для чего требуется n
шагов, умноженных на количество шагов в цикле. Этот цикл включает вложенный цикл for
, который выполняется 100 раз. То есть цикл for book выполняется 102
× n, или 102n раз. По- сле исключения коэффициента выясняется, что cheerForFavoriteBook()
все еще остается линейной операцией O(n). Коэффициент 102 может показаться слиш- ком большим, чтобы его игнорировать, но примите во внимание следующее: если favorite не встречается в списке books
, эта функция выполнит только 1n шагов.
Влияние коэффициентов может изменяться в таких пределах, что их трудно рас- сматривать как содержательные.
282
Глава 13.Измерение быстродействия и анализ сложности алгоритмов
Затем функция findDuplicateBooks()
просматривает список books
(линейная опе- рация) по одному разу для каждой книги (другая линейная операция):
def findDuplicateBooks(books):
for i in range(books): # n шагов for j in range(i + 1, books): # n шагов if books[i] == books[j]: # 1 шаг print('Duplicate:', books[i]) # 1 шаг
Цикл for i
перебирает весь список books
, выполняя шаги в цикле n раз. Цикл j
также перебирает часть списка books
, хотя из-за исключения коэффициентов это также считается операцией с линейным временем. То есть цикл for i
выполняет
n
× n операций, а именно n
2
. Как следствие, findDuplicateBooks()
является опера- цией с полиномиальным временем O(n
2
).
Вложенные циклы сами по себе не подразумевают полиномиальной операции, но такой сложностью обладают вложенные циклы, в которых оба цикла выполняют
n итераций. В результате будут выполнены n
2
шагов, а это подразумевает опера- цию O(n
2
).
Рассмотрим более сложный пример. Алгоритм бинарного поиска, упоминавшийся ранее, основан на поиске значения (назовем его needle
) в середине отсортирован- ного списка (назовем его haystack
)
1
. Если элемент needle не найден, мы переходим к поиску в первой или второй половине haystack в зависимости от того, в какой половине мы рассчитываем найти needle
. Процесс повторяется, поиск ведется в по- стоянно уменьшающихся половинах, либо пока не будет найден элемент needle
, либо пока не будет сделан вывод о том, что в haystack его нет. Обратите внимание: бинарный поиск работает только в том случае, если элементы haystack следуют в порядке сортировки.
def binarySearch(needle, haystack):
if not len(haystack): # 1 шаг return None # 1 шаг startIndex = 0 # 1 шаг endIndex = len(haystack) - 1 # 1 шаг haystack.sort() # ??? шагов while start <= end: # ??? steps midIndex = (startIndex + endIndex) // 2 # 1 шаг if haystack[midIndex] == needle: # 1 шаг
# Значение needle найдено.
return midIndex # 1 шаг elif needle < haystack[midIndex]: # 1 шаг
# Искать в первой половине.
1
Needle — иголка, haystack — стог сена (англ). — Примеч. ред.
Определение порядка сложности нотации «О-большое» вашего кода
283
endIndex = midIndex - 1 # 1 шаг elif needle > haystack[mid]: # 1 шаг
# Искать во второй половине.
startIndex = midIndex + 1 # 1 шаг
Две строки binarySearch()
оценить не так легко. Порядок «О-большое» вызова метода haystack.sort()
зависит от кода, находящегося в методе Python sort()
Найти этот код непросто, но в интернете можно поискать информацию о методе и узнать, что он выполняется с порядком O(n log n). (Все основные функции сорти- ровки выполняются в лучшем случае за время O(n log n).) Порядок «О-большое» для некоторых распространенных функций и методов Python описан в этой главе в разделе «Порядок “О-большое” для часто используемых функций».
Цикл while анализируется несколько сложнее, чем показанные выше циклы for
Чтобы определить, сколько итераций будет выполнено в цикле, необходимо пони- мать алгоритм бинарного поиска. До начала цикла startIndex и endIndex покрывают весь диапазон haystack
, а midIndex устанавливается в середину этого диапазона. При каждой итерации цикла while происходит одно из двух. Если haystack[midIndex]
==
needle
, искомое значение найдено и функция возвращает индекс needle в haystack
Если needle
<
haystack[midIndex]
или needle
>
haystack[midIndex]
, диапазон, покрываемый startIndex и endIndex
, сокращается вдвое — за счет изменения либо startIndex
, либо endIndex
. Число делений любого списка размера n надвое составляет log2(n). (К сожалению, это просто математический факт, который вы должны знать.) Таким образом, у цикла while порядок нотации «О-большое» со- ставляет O(log n).
Но так как порядок O(n log n) строки haystack.sort()
выше O(log n), более низкий порядок O(log n) исключается, а порядком всей функции binarySearch()
становится O(n log n). Если мы можем гарантировать, что binarySearch()
будет вызываться только с отсортированным списком haystack
, строку haystack.sort()
можно опустить и сделать binarySearch()
функцией O(log n). Формально это улучшает эффективность функции, но не делает всю программу более эффек- тивной, потому что необходимая работа по сортировке просто перемещается в другую часть программы. Многие реализации бинарного поиска опускают шаг сортировки, поэтому говорят, что алгоритм бинарного поиска обладает логариф- мической сложностью O(log n).
Порядок «О-большое» для часто используемых функций
Анализ эффективности вашего кода должен учитывать порядок сложности всех вызываемых функций. Если вы сами написали функцию, вы сможете проанали- зировать собственный код. Но чтобы найти порядок «О-большое» для встроенных функций и методов Python, приходится обращаться к спискам вроде приведенного ниже.
284
Глава 13.Измерение быстродействия и анализ сложности алгоритмов
В списке показаны порядки некоторых распространенных операций Python для типов последовательностей — таких как строки, кортежи и списки.
s[i]
reading и s[i]
=
value assignment
— операции O(1).
s.append(value)
— операция O(1).
s.insert(i,
value)
— операция O(n). Вставка значения в последовательность
(особенно в начало) требует сдвига всех элементов с индексами выше i
на одну позицию вверх в последовательности.
s.remove(value)
— операция O(n). Удаление значений из последовательности
(особенно в начале) требует сдвига всех элементов с индексами выше i
на одну позицию вниз в последовательности.
s.reverse()
— операция O(n), потому что необходимо переставить все эле- менты последовательности.
s.sort()
— операция O(n log n), потому что алгоритм сортировки Python имеет сложность O(n log n).
value in s
— операция O(n), потому что необходимо проверить каждый элемент.
for value in s:
— операция O(n).
len(s)
— операция O(1), потому что Python хранит количество элементов в последовательности, чтобы их не приходилось заново пересчитывать при каждом вызове len()
В следующем списке приведены порядки «О-большое» для некоторых распростра- ненных операций Python для типов отображений (таких как словари, множества и фиксированные множества).
m[key]reading и m[key]
=
value assignment
— операции O(1).
m.add(value)
— операция O(1).
value in m
— операция O(1) для словарей; выполняется намного быстрее, чем для последовательностей.
for key in m:
— операция O(n).
len(m)
— операция O(1), потому что Python хранит количество элементов в отображении, чтобы их не приходилось заново пересчитывать при каждом вызове len()
Если в списках элементы обычно приходится искать от начала до конца, словари ис- пользуют ключ для вычисления адреса, а время, необходимое для поиска значения
Определение порядка сложности нотации «О-большое» вашего кода
285
по ключу, остается постоянным. Способ вычисления называется алгоритмом хеши-
рования, а адрес — хеш-кодом. Тема хеширования выходит за рамки книги, но именно из-за него многие операции отображения выполняются с постоянным временем O(1).
Множества также используют хеширование, потому что множества по сути являются словарями, содержащими только ключи (вместо пар «ключ — значение»).
Но помните, что преобразование списка во множество является операцией O(n), так что преобразование списка во множество с последующим обращением к элементам множества не обеспечит никакого выигрыша.
Моментальный анализ сложности
Когда вы освоитесь с выполнением анализа «О-большое», вам не придется вы- полнять каждый из шагов. Через какое-то время вы сможете просто взглянуть на какие-то характерные особенности кода, чтобы быстро определить его порядок сложности.
Если обозначить переменной n размер данных, с которыми работает код, можно воспользоваться рядом общих правил.
Если код не обращается ни к каким данным, это O(1).
Если код последовательно перебирает данные, это O(1).
Если код содержит два вложенных цикла, каждый из которых перебирает данные, это O(n
2
).
Вызовы функций включаются в подсчеты не как один шаг, а как общее коли- чество шагов кода внутри функции. См. подраздел «Порядок “О-большое” для часто используемых функций», с. 283.
Если код содержит операцию «разделяй и властвуй», которая многократно делит данные надвое, это O(log n).
Если код содержит операцию «разделяй и властвуй», которая выполняется по одному разу для каждого элемента данных, это O(n log n).
Если код перебирает все возможные комбинации значений в данных с раз- мером n, это O(2
n
) или другой экспоненциальный порядок.
Если код перебирает все возможные перестановки (то есть варианты упоря- дочения) значений данных, это O(n!).
Если код включает сортировку данных, это как минимум O(n log n).
Эти правила станут хорошей отправной точкой для анализа, но они не заменят ре- ального анализа «О-большое». Помните, что порядок не является окончательным