сложность алгоритма функции set () и оператора «&» при совместном использовании - PullRequest
Новая
       27

сложность алгоритма функции set () и оператора «&» при совместном использовании

0 голосов
/ 23 января 2019

Я хочу вычислить значение этой строки кода (для поиска общих элементов в двух массивах) заданного размера n, но я не знаю, как set работает в Python.Также оператор "&" между ними.Может ли кто-нибудь помочь мне понять, что именно они делают? 

result = set(arr1) & set(arr2)

1 Ответ

0 голосов
/ 23 января 2019

Для двух наборов s1 и s2 в среднем оператор & равен O(min(len(s1), len(s2))

Оператор & вычисляет пересечение между двумя наборами.Это означает, что результирующий набор будет содержать только элементы из s1 и s2.

Например: 

{1, 2, 3, 4} & {3, 4, 5}

Выход: 

{3, 4}

операция примерно равна: 

def intersection(s1, s2):

    # make s1 the smaller set no matter what
    if len(s1) > len(s2): s1, s2 = s2, s1

    res = set()

    # iterate over all items in the smaller set and add if they are common to both sets
    for item in s1:
        if item in s2: res.add(item)
    return res

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

Итерирование по всем элементам в одном наборе - O(N), тогда как *Операция 1024 * занимает в среднем O(1), в результате чего общее время выполнения O(N).

Поскольку набор, который вы перебираете, на самом деле не имеет значения, python экономит некоторое время, перебирая меньший набор, чтобы сделатьN в O(N) как можно меньше, что приводит к сложности O(min(len(s1), len(s2)).

Обратите внимание, что это только средняя сложность случая.Наихудшая (но очень редкая) сложность для операции in составляет O(N), если каждый элемент в наборе каким-то образом имеет одинаковый хэш.Это дало бы операции & наихудший сценарий O(len(s1) * len(s2)) сложности

...