#python-3.x #performance #oop #time-complexity #big-o
Вопрос:
У меня есть 2 функции, которые выполняют одну и ту же задачу определения того, есть ли в 2 списках какой-либо общий элемент между ними. Я хочу проанализировать их временную сложность.
Что я знаю, так это то, что цикл for при повторении n раз дает O(n) сложность. Но меня смущает ситуация, когда мы используем оператор «в». например: если элемент в моем списке
Пожалуйста, ознакомьтесь с функциями, чтобы лучше понять сценарий:
list1 = ['a','b','c','d','e']
list2 = ['m','n','o','d']
def func1(list1, list2):
for i in list1: # O(n), assuming number of items in list1 is n
if i in list2: # What will be the BigO of this statement??
return True
return False
z = func1(list1, list2)
print(z)
У меня есть еще одна функция func2, пожалуйста, помогите определить ее значение:
def func2(list1, list2):
dict = {}
for i in list1:
if i not in dict.keys():
dict[i] = True
for j in list2:
if j in dict.keys():
return True
return False
z = func2(list1, list2)
print(z)
Какова временная сложность функций func1 и func2? Есть ли какая-либо разница в производительности между 2 функциями?
Комментарии:
1. Обратите внимание, что вторая функция должна использовать a
set
вместо adict
(и не использовать имя типа в качестве идентификатора). Хотяdict
ключи ведут себя как заданные, использование фиктивных значений для этой цели является расточительным иset
лучше оптимизировано для тестов на членство.
Ответ №1:
Относительно func1
:
- поиск в списках-это линейная операция по количеству элементов,
- предполагая, что элементы упорядочены случайным образом и порядок проверки также не связан, то статистически вы сталкиваетесь с существующим элементом за n/2 шага и n, когда он не найден (что упрощает до O(n))
if x in list_
является линейным поиском, как описано выше, следовательно func1
, имеет сложность n^2.
Относительно func2
:
вместо словаря вы можете рассмотреть возможность использования набора. Он имеет сложность O(1) для проверки существования элемента. что улучшило бы сложность func1
, а также вы можете использовать set(list)
для создания списка вместо итерации по списку непосредственно в python (что медленнее, чем инициализация набора непосредственно из списка, но не влияет на сложность O, так как она просто медленнее, но постоянна).
Комментарии:
1. Спасибо за объяснение, но я только что видел на » вики. python.org/moin/TimeComplexity » что проверка существования элемента (скажем, x в my_set) в наборе имеет сложность наихудшего случая O(n). Если это так, то даже вторая функция имеет сложность O(n^2). Пожалуйста, поправьте меня, если я что-то упускаю?
2. Это зависит от реализации набора, и даже в этом случае не путайте средний случай с наихудшим случаем. Сложность Big-O обычно выражается в средних терминах по области возможных случаев, а затем для Python и множеств она равна O(n) в среднем. Пожалуйста, ознакомьтесь с подробностями.