Я пытаюсь научить себя, как рассчитать нотацию BigO для произвольной функции. Я нашел эту функцию в учебнике. В книге утверждается, что функция O (n 2 ). Это объясняет, почему это так, но я изо всех сил стараюсь следовать. Интересно, сможет ли кто-нибудь показать мне математику, почему это так? По сути, я понимаю, что это нечто меньшее, чем O (n 3 ), но я не мог самостоятельно приземлиться на O (n 2 )
Предположим, нам даны три последовательности чисел, A, B и C. Предположим, что ни одна отдельная последовательность не содержит повторяющихся значений, но могут существовать некоторые числа в двух или трех последовательностях. Задача дизъюнктности трехстороннего множества состоит в том, чтобы определить, является ли пересечение трех последовательностей пустым, а именно, что нет элемента x такого, что x ∈ A, x ∈ B и x ∈ C.
Между прочим, для меня это не домашнее задание - этот корабль отплыл много лет назад :), просто я пытаюсь стать умнее.
def disjoint(A, B, C):
"""Return True if there is no element common to all three lists."""
for a in A:
for b in B:
if a == b: # only check C if we found match from A and B
for c in C:
if a == c # (and thus a == b == c)
return False # we found a common value
return True # if we reach this, sets are disjoint
[Редактировать] Согласно учебнику:
В улучшенной версии мы не просто экономим время, если нам везет. Мы утверждаем, что в наихудшем случае для дизъюнкта является O (n 2 ).
Объяснение книги, которому я изо всех сил стараюсь следовать, таково:
Чтобы учесть общее время выполнения, мы исследуем время, затраченное на выполнение каждой строки кода. Управление циклом for над A требует времени O (n). Управление циклом for over B составляет в общей сложности O (n 2 ) времени, поскольку этот цикл выполняется n раз. Тест a == b оценивается O (n 2 ) раз. Оставшееся время зависит от того, сколько совпадающих пар (a, b) существует. Как мы уже отмечали, таких пар не более n, и поэтому управление циклом над C и командами в теле этого цикла используют не более O (n 2 ) времени. Общее потраченное время составляет O (n 2 ).
(И чтобы отдать должное ...) Книга: Структуры данных и алгоритмы в Python, Майкл Т. Гудрич и др. все, Wiley Publishing, стр. 135
[Править] Обоснование; Ниже приведен код перед оптимизацией:
def disjoint1(A, B, C):
"""Return True if there is no element common to all three lists."""
for a in A:
for b in B:
for c in C:
if a == b == c:
return False # we found a common value
return True # if we reach this, sets are disjoint
Выше вы можете ясно увидеть, что это O (n 3 ), потому что каждый цикл должен работать в полную силу. В книге утверждается, что в упрощенном примере (приведенном вначале) третий цикл представляет собой сложность только O (n 2 ), поэтому уравнение сложности имеет вид k + O (n 2 ) + O (n 2 ), что в конечном итоге дает O (n 2 ).
Хотя я не могу доказать, что это так (таким образом, вопрос), читатель может согласиться, что сложность упрощенного алгоритма, по крайней мере, меньше, чем оригинал.
[Редактировать] И доказать, что упрощенная версия является квадратичной:
if __name__ == '__main__':
for c in [100, 200, 300, 400, 500]:
l1, l2, l3 = get_random(c), get_random(c), get_random(c)
start = time.time()
disjoint1(l1, l2, l3)
print(time.time() - start)
start = time.time()
disjoint2(l1, l2, l3)
print(time.time() - start)
Урожайность:
0.02684807777404785
0.00019478797912597656
0.19134306907653809
0.0007600784301757812
0.6405444145202637
0.0018095970153808594
1.4873297214508057
0.003167390823364258
2.953308343887329
0.004908084869384766
Поскольку второе различие равно, упрощенная функция действительно квадратична:
[Править] И еще одно доказательство:
Если я предполагаю худший случай (A = B! = C),
if __name__ == '__main__':
for c in [10, 20, 30, 40, 50]:
l1, l2, l3 = range(0, c), range(0,c), range(5*c, 6*c)
its1 = disjoint1(l1, l2, l3)
its2 = disjoint2(l1, l2, l3)
print(f"iterations1 = {its1}")
print(f"iterations2 = {its2}")
disjoint2(l1, l2, l3)
выходы:
iterations1 = 1000
iterations2 = 100
iterations1 = 8000
iterations2 = 400
iterations1 = 27000
iterations2 = 900
iterations1 = 64000
iterations2 = 1600
iterations1 = 125000
iterations2 = 2500
При использовании второго разностного теста наихудший результат является точно квадратичным.
Ответы:
Книга действительно верна, и она дает хороший аргумент. Обратите внимание, что время не является надежным индикатором алгоритмической сложности. Временные интервалы могут учитывать только специальное распределение данных, или контрольные примеры могут быть слишком малы: алгоритмическая сложность описывает только то, как использование ресурсов или время выполнения масштабируются за пределы какого-либо достаточно большого входного размера.
В книге утверждается, что сложность равна O (n²), потому что
if a == b
ветвь вводится не более n раз. Это неочевидно, потому что циклы все еще пишутся как вложенные. Это более очевидно, если мы извлечем это:Этот вариант использует генераторы для представления промежуточных результатов.
AB
у нас будет не более n элементов (из-за гарантии того, что входные списки не будут содержать дубликаты), а создание генератора требует сложности O (n²).ABC
включает цикл по генераторуAB
длины n иC
длине n , так что его алгоритмическая сложность также составляет O (n²).Поскольку пары входных списков можно проверять последовательно, из этого следует, что определение того, является ли любое количество списков непересекающимися, может быть выполнено за O (n²) времени.
Этот анализ неточен, поскольку предполагает, что все списки имеют одинаковую длину. Более точно можно сказать, что он
AB
имеет не более длины min (| A |, | B |), а его создание имеет сложность O (| A | • | B |). ПроизводствоABC
имеет сложность O (min (| A |, | B |) • | C |). Общая сложность зависит от того, как упорядочены входные списки. С | A | ≤ | B | ≤ | C | мы получаем полную сложность O (| A | • | C |) в худшем случае.Обратите внимание, что выигрыш в эффективности возможен, если входные контейнеры позволяют проводить быстрые тесты членства, а не выполнять итерации по всем элементам. Это может быть в случае, когда они сортируются так, чтобы можно было выполнить двоичный поиск, или когда они являются хэш-наборами. Без явных вложенных циклов это будет выглядеть так:
или в генераторной версии:
источник
n
переменную и поговорили о реальных переменных в игре.len(a) == len(b) == len(c)
, хотя это верно в контексте анализа сложности времени, имеет тенденцию запутывать разговор.Обратите внимание, что если все элементы различны в каждом предполагаемом списке, вы можете повторять C только один раз для каждого элемента в A (если есть элемент в B, который равен). Таким образом, внутренний цикл O (n ^ 2) всего
источник
это очень важная часть информации.
В противном случае наихудшим вариантом оптимизированной версии по-прежнему будет O (n³), когда A и B равны и содержат один элемент, дублированный n раз:
какие выводы:
Таким образом, в основном, авторы предполагают, что наихудшего случая O (n³) не должно произойти (почему?), И «доказывают», что наихудшим случаем сейчас является O (n²).
Реальной оптимизацией было бы использование наборов или диктов для проверки включения в O (1). В этом случае
disjoint
будет O (n) для каждого входа.источник
key in dict
, как и авторы. : - / В свою защиту, я думаю, что гораздо сложнее найти диктат сn
ключами иn
коллизиями хешей, чем просто создать список сn
дублированными значениями. И с набором или dict действительно не может быть никакого дублированного значения. Таким образом, наихудший-худший случай действительно O (n²). Я обновлю свой ответ.Чтобы поместить вещи в термины, которые использует ваша книга:
Я думаю, у вас нет проблем с пониманием того, что проверка на
a == b
худший случай O (n 2 ).Теперь в худшем случае для третьего контура, каждый
a
вA
имеет матч вB
, так что третий цикл будет вызываться каждый раз. В случае, когдаa
не существует вC
, он будет проходить через весьC
набор.Другими словами, это 1 раз за каждый
a
и 1 раз за каждыйc
или n * n. O (n 2 )Итак, есть O (n 2 ) + O (n 2 ), на которые указывает ваша книга.
источник
Хитрость оптимизированного метода заключается в том, чтобы срезать углы. Только если a и b совпадают, c будет уделено внимание. Теперь вы можете предположить, что в худшем случае вам все равно придется оценивать каждое c. Это неправда.
Вы, наверное, думаете, что наихудший случай, когда каждая проверка для a == b приводит к запуску над C, потому что каждая проверка для a == b возвращает совпадение. Но это невозможно, потому что условия для этого противоречивы. Чтобы это работало, вам нужны A и B, которые содержат одинаковые значения. Они могут быть упорядочены по-разному, но каждое значение в A должно иметь совпадающее значение в B.
Теперь вот кикер. Невозможно организовать эти значения так, чтобы для каждого a вам приходилось оценивать все b, прежде чем вы найдете свое соответствие.
Это будет сделано мгновенно, потому что соответствующие 1 являются первым элементом в обеих сериях. Как насчет
Это сработало бы для первого прохода над A: только последний элемент в B дал бы удар. Но следующая итерация по A уже должна быть быстрее, потому что последняя точка в B уже занята 1. И действительно, на этот раз это займет всего четыре итерации. И это становится немного лучше с каждой следующей итерацией.
Теперь я не математик, поэтому я не могу доказать, что это закончится в O (n2), но я чувствую это на своих сабо.
источник
O(n^2)
цикла; который дает общееO(n^2)
(константы игнорируются).Сначала был озадачен, но ответ Амона действительно полезен. Я хочу посмотреть, смогу ли я сделать действительно краткую версию:
Для заданного значения
a
inA
функция сравниваетсяa
со всеми возможнымиb
inB
, и она делает это только один раз. Так что для данногоa
он выполняетa == b
ровноn
раз.B
не содержит дубликатов (ни один из списков не содержит), поэтому для заданногоa
будет не более одного совпадения. (Это ключ). Там, где есть совпадение,a
будут сравниваться все возможныеc
, что означает, чтоa == c
это выполняется ровно n раз. Там, где нет совпадений,a == c
вообще не бывает.Так что для данного
a
есть либоn
сравнения, либо2n
сравнения. Это происходит для каждогоa
, поэтому лучший возможный случай - (n²), а худший - (2n²).TLDR: каждое значение
a
сравнивается с каждым значениемb
и против каждого значенияc
, но не против каждой комбинации изb
иc
. Две проблемы складываются вместе, но они не умножаются.источник
Подумайте об этом так, некоторые числа могут быть в двух или трех последовательностях, но средний случай этого состоит в том, что для каждого элемента в наборе A исчерпывающий поиск выполняется в b. Гарантируется, что каждый элемент в наборе A будет повторяться, но подразумевается, что будет перебираться менее половины элементов в наборе b.
Когда элементы в наборе b итерируются, итерация происходит, если есть совпадение. это означает, что средний случай для этой непересекающейся функции равен O (n2), но абсолютным худшим случаем для нее может быть O (n3). Если книга не будет вдаваться в подробности, она, вероятно, даст вам средний случай в качестве ответа.
источник