Почему наихудший случай для этой функции O (n ^ 2)?

44

Я пытаюсь научить себя, как рассчитать нотацию 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

При использовании второго разностного теста наихудший результат является точно квадратичным.

введите описание изображения здесь

SteveJ
источник
6
Либо книга неверна, либо ваша транскрипция ошибочна.
Candied_Orange
6
Нет. Неправильно не так, независимо от того, как хорошо цитируется. Либо объясните, почему мы не можем просто принять их, если они пойдут наихудшим путем, чем они могут при проведении большого анализа О, или принять результаты, которые вы получаете.
Candied_Orange
8
@candied_orange; Я добавил еще одно оправдание в меру своих способностей - не в моей сильной стороне. Я бы попросил вас снова допустить возможность того, что вы действительно ошибаетесь. Вы сделали свою точку зрения, должным образом приняты.
SteveJ
8
Случайные числа не ваш худший случай. Это ничего не доказывает.
Теластин
7
ааа. Хорошо. «Нет последовательности с повторяющимися значениями» меняет наихудший случай, так как C может срабатывать только один раз для любого A. Извините за разочарование - вот что я получаю за то, что нахожусь на stackexchange поздно вечером в субботу: D
Telastyn

Ответы:

63

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

В книге утверждается, что сложность равна O (n²), потому что if a == bветвь вводится не более n раз. Это неочевидно, потому что циклы все еще пишутся как вложенные. Это более очевидно, если мы извлечем это:

def disjoint(A, B, C):
  AB = (a
        for a in A
        for b in B
        if a == b)
  ABC = (a
         for a in AB
         for c in C
         if a == c)
  for a in ABC:
    return False
  return True

Этот вариант использует генераторы для представления промежуточных результатов.

  • В генераторе ABу нас будет не более n элементов (из-за гарантии того, что входные списки не будут содержать дубликаты), а создание генератора требует сложности O (n²).
  • Создание генератора ABCвключает цикл по генератору ABдлины n и Cдлине n , так что его алгоритмическая сложность также составляет O (n²).
  • Эти операции не являются вложенными, но выполняются независимо, поэтому общая сложность составляет O (n² + n²) = O (n²).

Поскольку пары входных списков можно проверять последовательно, из этого следует, что определение того, является ли любое количество списков непересекающимися, может быть выполнено за O (n²) времени.

Этот анализ неточен, поскольку предполагает, что все списки имеют одинаковую длину. Более точно можно сказать, что он ABимеет не более длины min (| A |, | B |), а его создание имеет сложность O (| A | • | B |). Производство ABCимеет сложность O (min (| A |, | B |) • | C |). Общая сложность зависит от того, как упорядочены входные списки. С | A | ≤ | B | ≤ | C | мы получаем полную сложность O (| A | • | C |) в худшем случае.

Обратите внимание, что выигрыш в эффективности возможен, если входные контейнеры позволяют проводить быстрые тесты членства, а не выполнять итерации по всем элементам. Это может быть в случае, когда они сортируются так, чтобы можно было выполнить двоичный поиск, или когда они являются хэш-наборами. Без явных вложенных циклов это будет выглядеть так:

for a in A:
  if a in B:  # might implicitly loop
    if a in C:  # might implicitly loop
      return False
return True

или в генераторной версии:

AB = (a for a in A if a in B)
ABC = (a for a in AB if a in C)
for a in ABC:
  return False
return True
Амон
источник
4
Это было бы намного понятнее, если бы мы просто отменили эту магическую nпеременную и поговорили о реальных переменных в игре.
Александр
15
@ code_dredd Нет, это не так, у него нет прямой связи с кодом. Это абстракция, которая предполагает, что len(a) == len(b) == len(c), хотя это верно в контексте анализа сложности времени, имеет тенденцию запутывать разговор.
Александр
10
Возможно, достаточно сказать, что код OP имеет наихудший вариант сложности O (| A | • | B | + min (| A |, | B |) • | C |), чтобы вызвать понимание?
Пабло Х
3
Еще одна вещь о временных тестах: как вы узнали, они не помогли вам понять, что происходит. С другой стороны, они, кажется, дали вам дополнительную уверенность в противостоянии различным неправильным, но убедительно заявленным утверждениям, что книга явно была неправильной, так что это хорошо, и в этом случае ваше тестирование превзошло интуитивное махание рукой ... Для понимания, более эффективным способом тестирования было бы запустить его в отладчике с точками останова (или добавить распечатки значений переменных) в начале каждого цикла.
Сденхэм
4
«Обратите внимание, что время не является полезным индикатором алгоритмической сложности». Я думаю, что это было бы более точным, если бы оно говорило «строгий» или «надежный», а не «полезный».
накопление
7

Обратите внимание, что если все элементы различны в каждом предполагаемом списке, вы можете повторять C только один раз для каждого элемента в A (если есть элемент в B, который равен). Таким образом, внутренний цикл O (n ^ 2) всего

Риад
источник
3

Мы будем предполагать, что ни одна отдельная последовательность не содержит дубликатов.

это очень важная часть информации.

В противном случае наихудшим вариантом оптимизированной версии по-прежнему будет O (n³), когда A и B равны и содержат один элемент, дублированный n раз:

i = 0
def disjoint(A, B, C):
    global i
    for a in A:
        for b in B:
            if a == b:
                for c in C:
                    i+=1
                    print(i)
                    if a == c:
                        return False 
    return True 

print(disjoint([1] * 10, [1] * 10, [2] * 10))

какие выводы:

...
...
...
993
994
995
996
997
998
999
1000
True

Таким образом, в основном, авторы предполагают, что наихудшего случая O (n³) не должно произойти (почему?), И «доказывают», что наихудшим случаем сейчас является O (n²).

Реальной оптимизацией было бы использование наборов или диктов для проверки включения в O (1). В этом случае disjointбудет O (n) для каждого входа.

Эрик Думинил
источник
Ваш последний комментарий довольно интересный, не думал об этом. Вы предполагаете, что это связано с тем, что вы можете сделать три O (n) операции последовательно?
SteveJ
2
Если вы не получите идеальный хэш с хотя бы одним сегментом на элемент ввода, вы не сможете проверить включение в O (1). Сортированный набор обычно имеет O (log n). Если вы не говорите о средней стоимости, но вопрос не в этом. Тем не менее, иметь сбалансированный двоичный набор, получая жесткий O (n log n), тривиально.
Ян Дорняк
@JanDorniak: Отличный комментарий, спасибо. Теперь это немного неловко: я проигнорировал худший вариант key in dict, как и авторы. : - / В свою защиту, я думаю, что гораздо сложнее найти диктат с nключами и nколлизиями хешей, чем просто создать список с nдублированными значениями. И с набором или dict действительно не может быть никакого дублированного значения. Таким образом, наихудший-худший случай действительно O (n²). Я обновлю свой ответ.
Эрик Думинил
2
@JanDorniak Я думаю, что множества и dicts - это хеш-таблицы в python, а не красно-черные деревья в C ++. Таким образом, абсолютный наихудший случай хуже, до 0 (n) для поиска, но средний случай - O (1). В отличие от O (log n) для C ++ wiki.python.org/moin/TimeComplexity . Учитывая, что это вопрос по питону, и что область проблемы приводит к высокой вероятности средней производительности случая, я не думаю, что утверждение O (1) является плохим.
Балдрикк
3
Я думаю, что вижу проблему здесь: когда авторы говорят: «мы будем предполагать, что ни одна отдельная последовательность не содержит повторяющихся значений», это не является шагом в ответе на вопрос; скорее это предварительное условие, при котором вопрос будет решаться. В педагогических целях это превращает неинтересную проблему в проблему, которая бросает вызов интуиции людей в отношении big-O - и, похоже, в этом она преуспела, судя по количеству людей, которые настаивали на том, что O (n²) должно быть ошибочным. Кроме того, хотя это спорный вопрос, подсчет количества шагов в одном примере не является объяснением.
Сденхэм
3

Чтобы поместить вещи в термины, которые использует ваша книга:

Я думаю, у вас нет проблем с пониманием того, что проверка на 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 ), на которые указывает ваша книга.

Марс
источник
0

Хитрость оптимизированного метода заключается в том, чтобы срезать углы. Только если a и b совпадают, c будет уделено внимание. Теперь вы можете предположить, что в худшем случае вам все равно придется оценивать каждое c. Это неправда.

Вы, наверное, думаете, что наихудший случай, когда каждая проверка для a == b приводит к запуску над C, потому что каждая проверка для a == b возвращает совпадение. Но это невозможно, потому что условия для этого противоречивы. Чтобы это работало, вам нужны A и B, которые содержат одинаковые значения. Они могут быть упорядочены по-разному, но каждое значение в A должно иметь совпадающее значение в B.

Теперь вот кикер. Невозможно организовать эти значения так, чтобы для каждого a вам приходилось оценивать все b, прежде чем вы найдете свое соответствие.

A: 1 2 3 4 5
B: 1 2 3 4 5

Это будет сделано мгновенно, потому что соответствующие 1 являются первым элементом в обеих сериях. Как насчет

A: 1 2 3 4 5
B: 5 4 3 2 1

Это сработало бы для первого прохода над A: только последний элемент в B дал бы удар. Но следующая итерация по A уже должна быть быстрее, потому что последняя точка в B уже занята 1. И действительно, на этот раз это займет всего четыре итерации. И это становится немного лучше с каждой следующей итерацией.

Теперь я не математик, поэтому я не могу доказать, что это закончится в O (n2), но я чувствую это на своих сабо.

Мартин Маат
источник
1
Порядок элементов здесь не играет роли. Важным требованием является отсутствие дубликатов; аргументом является то, что циклы могут быть преобразованы в два отдельных O(n^2)цикла; который дает общее O(n^2)(константы игнорируются).
AnoE
@AnoE Действительно, порядок элементов не имеет значения. Это именно то, что я демонстрирую.
Мартин Маат
Я вижу, что вы пытаетесь сделать, и то, что вы пишете, не является неправильным, но с точки зрения ОП ваш ответ в основном показывает, почему конкретный ход мыслей не имеет значения; это не объясняет, как прийти к фактическому решению. ОП, похоже, не дает понять, что он на самом деле думает, что это связано с порядком. Поэтому мне неясно, как этот ответ поможет ОП.
AnoE
-1

Сначала был озадачен, но ответ Амона действительно полезен. Я хочу посмотреть, смогу ли я сделать действительно краткую версию:

Для заданного значения ain Aфункция сравнивается aсо всеми возможными bin B, и она делает это только один раз. Так что для данного 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. Две проблемы складываются вместе, но они не умножаются.

Дуглас Виншип
источник
-3

Подумайте об этом так, некоторые числа могут быть в двух или трех последовательностях, но средний случай этого состоит в том, что для каждого элемента в наборе A исчерпывающий поиск выполняется в b. Гарантируется, что каждый элемент в наборе A будет повторяться, но подразумевается, что будет перебираться менее половины элементов в наборе b.

Когда элементы в наборе b итерируются, итерация происходит, если есть совпадение. это означает, что средний случай для этой непересекающейся функции равен O (n2), но абсолютным худшим случаем для нее может быть O (n3). Если книга не будет вдаваться в подробности, она, вероятно, даст вам средний случай в качестве ответа.

Эдди Экпо
источник
4
В книге совершенно ясно, что O (n2) - наихудший случай, а не средний случай.
SteveJ
Описание функции в терминах обозначений больших О обычно дает только верхнюю границу скорости роста функции. С большими обозначениями O связаны несколько связанных обозначений, использующих символы o, Ω, ω и Θ, чтобы описать другие виды оценок асимптотических скоростей роста. Википедия - Big O
candied_orange
5
«Если книга не вдавалась в подробности, она, вероятно, даст вам средний случай в качестве ответа». Хм, нет. Без какой-либо явной оговорки мы обычно говорим о сложности шага наихудшего случая в модели ОЗУ. Когда мы говорим об операциях над структурами данных, и это ясно из контекста, то мы можем говорить об амортизированной сложности шага наихудшего случая в модели ОЗУ. Без явной квалификации мы обычно не будем говорить о лучшем случае, среднем случае, ожидаемом случае, сложности времени или любой другой модели, кроме ОЗУ.
Йорг Миттаг