Блог

У меня есть 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 функциями?

Относительно func1 :

• поиск в списках-это линейная операция по количеству элементов,
• предполагая, что элементы упорядочены случайным образом и порядок проверки также не связан, то статистически вы сталкиваетесь с существующим элементом за n/2 шага и n, когда он не найден (что упрощает до O(n))

if x in list_ является линейным поиском, как описано выше, следовательно func1 , имеет сложность n^2.

Относительно func2 :

вместо словаря вы можете рассмотреть возможность использования набора. Он имеет сложность O(1) для проверки существования элемента. что улучшило бы сложность func1 , а также вы можете использовать set(list) для создания списка вместо итерации по списку непосредственно в python (что медленнее, чем инициализация набора непосредственно из списка, но не влияет на сложность O, так как она просто медленнее, но постоянна).