Правильно ли говорить, что этот алгоритм O (n + m)?

Во-первых, я рассмотрел следующие вопросы:

O (N + M) временная сложность
Сравнивая сложность O (n + m) и O (max (n, m))
Big-O этих вложенных циклов
Является ли эта функция O (N + M) или O (N * M)?
Как найти временную сложность алгоритма

Тем не менее, я все еще не уверен на 100%. Тем не менее, у меня есть следующий код примера python:

adjList = [[4,7,8,9],[7,7,5,6],[1,4,3],[2,9],[2,1,7]] for i in adjList: for j in i: print "anything else" 

Я пришел к выводу, что это алгоритм O (n + m), вот мои рассуждения:

У меня есть adjList, который является списком списков. Целые числа случайным образом выбираются для примера. Это фактически список смежности, где вершина 1 связана с вершинами 4, 7, 8 и 9 и т. Д.

Я знаю, что adjList [i] [j] вернет j-й элемент из i-го списка. Поэтому adjList [0] [2] равен 8

Первая из них будет проходить через каждый из i-х списков. Если у нас есть N списков, это O (N) .

Второй из них будет перебирать каждый из j элементов списка. Но в этом случае j не является фиксированным значением, например, первый список имеет 4 элемента (4,7,8,9), а третий имеет 3 элемента (1,4,3). Таким образом, в конце вторая для будет петля М раз, М является суммой каждого из разных значений j. Итак, M – сумма элементов каждого списка. Таким образом, O (M)

В этом примере первый цикл должен быть 5 раз, а второй для цикла должен быть 16 раз. Всего 21 цикл. Если я изменю adjList на один большой список в списке, например:

 adjList = [[4,7,8,9,7,7,5,6,1,4,3,2,9,2,1,7]] 

Он по-прежнему будет проходить через 16 элементов во втором для плюс 1 раз для первого .

Тем самым я могу сказать, что алгоритм будет цикл N раз плюс М раз. Где N – количество списков в adjList, а M – сумма элементов в каждом из списков внутри adjList. Таким образом, O (N + M)

Итак, где мои сомнения?
В любом месте, где я смотрел, я нашел примеры вложенных циклов: O (N ^ 2) или O (N * M) . Даже когда люди упоминают, что они могут быть чем-то другим, кроме тех, которых я не нашел ни одного примера. Я еще не нашел пример вложенных циклов O (N + M). Поэтому я все еще сомневаюсь, что мои рассуждения верны.

Часть меня задается вопросом, не является ли это алгоритмом O (N * M). Но я не стал бы подробно останавливаться на этом.
Таким образом, остаются мои окончательные вопросы : верно ли это рассуждение, и указанный алгоритм действительно O (N + M)? Если нет, позаботьтесь о том, где мои ошибки?

Ваша большая ошибка в том, что вы четко не определили M и N, что означает.

Например:

  • Посещение всех ячеек в матрице N x M равно O(N*M) .
  • Если вы спрячете эту матрицу в список с ячейками P, посещение – O(P) .
  • Однако P == N*M в этом контексте … так что O(M*N) и O(P) означают то же самое … в этом контексте .

Глядя на ваши рассуждения, вы, кажется, скомпоновали (ваш) M с аналогом моего П. (я говорю аналог, потому что прямоугольные и оборванные массивы не идентичны.)

Итак, M – сумма элементов каждого списка.

Это не то, как я использовал M. Что еще более важно, не то, как различные другие ссылки, на которые вы смотрели, используют M. В частности, те, которые говорят о матрице N x M или массиве N x avge (M). Отсюда ваше замешательство.

Обратите внимание, что ваши M и N не являются независимыми переменными / параметрами. Если вы масштабируете проблему в N, это неявно изменяет значение M.

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

Вы определяете N и M следующим образом:

Тем самым я могу сказать, что алгоритм будет цикл N раз плюс М раз. Где N – количество списков в adjList, а M – сумма элементов в каждом из списков внутри adjList. Таким образом, O (N + M)

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

 list1 = [1, 2, 3] list2 = [4, 5] 

Итак, вы хотите посмотреть на все шесть из этих пар:

 pairs = [(1, 4), (2, 4), (3, 4), (1, 5), (2, 5), (3, 5)] 

Это всего 3 * 2 = 6. Теперь обобщите это; Например, list1 имеет N элементов, а list2 имеет M элементов. Общее число пар равно N * M, и поэтому это будет алгоритм O (N * M).

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

 items = [1, 2, 3, 4, 5] 

Это всего 3 + 2 = 5 предметов. Теперь обобщаем; вы получите N + M, и поэтому это будет алгоритм O (N + M).

Учитывая это, мы должны ожидать, что ваш случай и вышеуказанный случай будут идентичными, если ваш случай действительно O (N + M). Другими словами, мы должны ожидать, что ваше дело привлечет внимание ко всем предметам из двух разных списков. Но посмотрите:

 all_lists = [[4,7,8,9],[7,7,5,6],[1,4,3],[2,9],[2,1,7]] 

Это то же самое, что:

 list1 = [4,7,8,9] list2 = [7,7,5,6] list3 = [1,4,3] list4 = [2,9] list5 = [2,1,7] 

В то время как в случае O (N + M) было только два списка, здесь есть пять списков! Таким образом, это не может быть O (N + M).

Однако это должно дать вам представление о том, как разработать более качественное описание. (Подсказка: он может включать J, K и L, в дополнение к M и N.)

Происхождение вашей ошибки состоит в том, что в первых двух примерах M и N определены как отдельные друг от друга, но ваши определения M и N перекрываются. Чтобы M и N были суммированы или умножены значимо, они должны быть не связаны друг с другом. Но в ваших определениях значения M и N взаимосвязаны, и поэтому в некотором смысле они повторяют значения, которые не следует повторять.

Или, говоря иначе, предположим, что сумма длин всех внутренних списков добавляется до M. Если вам нужно сделать два шага вместо одного для каждого из этих значений, результат остается только константой значение C раз M. И для любого постоянного значения C, C * O (M) все еще O (M). Таким образом, работа, которую вы выполняете во внешнем цикле, уже подсчитывается (с точностью до постоянного множителя) с помощью термина O (M).

Заметки:

1. Хорошо, хорошо, не совсем, как указывает Стефан Похманн . Из-за техничности может быть более уместным сказать O (max (N, M)), потому что, если любые внутренние списки пустые, вам все равно придется их посещать.

Если ваш код выглядит так:

 for i in adjList: <something significant 1> for j in i: <something significant 2> 

Тогда я согласился бы с тобой. Однако <something significant 1> отсутствует (внутренняя работа python для выполнения цикла не стоит рассматривать), и поэтому нет причин включать O(N) часть. Нотация Big O не предназначена для подсчета каждой вещи, она показывает, как алгоритм масштабируется по мере увеличения входных данных. Поэтому мы рассмотрим, что важно, и это означает, что ваш код следует рассматривать как O(M) .

Причина, по которой вложенные петли обычно считаются O(N*M) состоит в том, что обычно N определяется как число итераций внешнего цикла (как вы это сделали), а M определяется как число итераций внутреннего цикла на внешний итерации, а не в целом . Поэтому N*M по общему определению равно M в вашем определении.

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

 from time import time start = time() L = [[] for _ in range(10000000)] construction_time = time() - start start = time() for sub in L: for i in sub: pass loop_time = time() - start print(construction_time / loop_time) # typically between 3 and 4