Блог

Главная - Вопросы по программированию - В Python, почему временные сложности различаются между заданными операциями объединения, пересечения и симметричной разности?

В Python, почему временные сложности различаются между заданными операциями объединения, пересечения и симметричной разности?

#python #algorithm #data-structures #set #time-complexity

#python #алгоритм #структуры данных #установить #временная сложность

Вопрос:

Согласно python wiki , это средние временные сложности для следующих операций набора между 2 наборами s и t:

  • объединение: O (s t)
  • пересечение: O(min (s, t))
  • разница: O (s)
  • симметричная разница: O (s)

Временные сложности для пересечения и различия имеют смысл для меня, но я не понимаю, почему временные сложности для объединения и симметричного различия не совпадают с временной сложностью для пересечения (O (min (s, t)).

Если бы мы назвали s меньшим набором, а t большим набором, то разве следующая логика для объединения и симметричной разности не имела бы временных сложностей (O(min (s, t))? Если это не так, как эти 2 операции выполняются под капотом в Python, то почему это?

 # Symmetric Difference
for element in s:
  if element in t:
    t.remove(element)
  else:
    t.add(element)
return t

# Union
for element in s:
  t.add(element)
return t

Комментарии:

1. Разве объединение не добавляло бы каждый элемент каждого набора в новый набор ? Не просто добавление каждого элемента одного набора в другой. Итак, O(len (s) len (t)) имеет смысл.

2. Объединение двух множеств, по крайней мере, такое же большое, как и любой аргумент. Это могло бы помочь, если бы я сказал вам, что O(s t) это другой способ записи O(max(s, t)) .

3. Симметричное различие не изменяет set t ; оно создает новый набор на основе поиска каждого значения s в t . Подумайте о том, сколько поисков это влечет за собой, и какова сложность каждого поиска.

4. @chepner Разве симметричная разница не должна принимать значение O (s t)? В конце концов, это симметрично. Не может зависеть только от одного, но не от другого.

5. @superbrain Да, я думал об асимметричной разнице. Я отмечу, однако, что в среднем s больший набор составляет половину времени, так что O(s t) == O(s) 🙂

Ответ №1:

Объединение

Рассмотрим два набора s и t . Чтобы создать новый набор, который представляет объединение s и t , вам нужно выполнить итерацию по ним. Это приводит к временной сложности O(len(s) len(t)) .

 def union(s, t):
   """Simple example for union, ignoring error-handling on inputs, etc."""
   result = set(s)   # copy: O(len(s))
   for el in t:      # iterate over t: O(len(t))
      result.add(el) # ignoring collisions, O(1) amortized time
   return result

Симметричная разница

 def symmetric_difference(s, t):
   """Simple example for symmetric difference, ignoring error-handling on inputs, etc."""
   result = set(t)        # copy: O(len(t))
   for el in s:           # iterate over s: O(len(s))
      if el not in t:    
        result.add(el)
      else:
        result.remove(el)
   return result

Что делает CPython, это начать с копии t , затем выполнить итерацию s и добавить или удалить элемент из выходного набора в соответствии с результатом поиска.
Также в этом случае предполагается, что амортизированная временная сложность для поиска равна O (1), результирующая временная сложность должна быть O(len(s) len(t)) , как и для объединения.

В таблице указана разная временная сложность для средней временной сложности симметричной разности как O(s) , и причина может заключаться в том, что они игнорируют временную сложность make_new_set функции (которая создает новый набор, начиная с t ).