Временная сложность решения задачи четырех сумм? - PullRequest
Новая
       94

Временная сложность решения задачи четырех сумм?

2 голосов
/ 09 мая 2020

Учитывая массив целых чисел, найдите все уникальные квартеты, суммируя их до указанного целого числа.

Я приведу два разных решения ниже, мне просто интересно, какое из них было более эффективным с относительно временной сложности?

Решение 1: 

def four_sum(arr, s): 
    n = len(arr)
    output = set()

    for i in range(n-2):       
        for j in range(i+1, n-1):
            seen = set()

            for k in range(j+1, n):
                target = s - arr[i] - arr[j] - arr[k]
                if target in seen:
                    output.add((arr[i], arr[j], arr[k], target))

                else:
                    seen.add(arr[k])

    return print('\n'.join(map(str, list(output))))

Я знаю, что это имеет временную сложность O(n^3).

Решение 2: 

def four_sum2(arr, s):
    n = len(arr)

    seen = {} 
    for i in range(n-1):
        for j in range(i+1, n):
            if arr[i] + arr[j] in seen:
                seen[arr[i] + arr[j]].add((i, j)) 
            else:
                seen[arr[i] + arr[j]] = {(i, j)} 

    output = set()

    for key in seen:
        if s - key in seen:
            for (i, j) in seen[key]:
                for (p, q) in seen[s - key]:
                    sorted_index = tuple(sorted((arr[i], arr[j], arr[p], arr[q]))) 

                    if i not in (p, q) and j not in (p, q): 
                        output.add(sorted_index)

    return output

Теперь первый блок имеет временную сложность O(n^2), но я не уверен, какова временная сложность второго блока?

1 Ответ

0 голосов
/ 10 мая 2020

TL; DR: сложность этого алгоритма O(n^4).

В первой части кортеж добавляется в seen для всей пары (i,j) где j>i . Таким образом, количество кортежей в seen составляет примерно (n-1)*n/2 = O(n^2), как вы догадываетесь.

Вторая часть немного сложнее. Если мы проигнорируем первое условие вложенных циклов (критический случай), два первых цикла могут перебирать все возможные кортежи в seen. Таким образом сложность не менее O(n^2). Для третьего l oop это немного сложно: трудно понять сложность, не делая никаких предположений о входных данных. Однако мы можем предположить, что теоретически существует критический случай, когда seen[s - key] содержит O(n^2) кортежей. В таком случае общий алгоритм будет работать в O(n^4)!

Практичен ли этот теоретический критический случай? К сожалению, да. В самом деле, возьмите для примера ввод arr = [5, 5, ..., 5, 5] с s = 20. Карта seen будет содержать один ключ (10), связанный с массивом с (n-1)*n/2 = O(n^2) элементами. В этом случае два первых цикла второй части будут выполняться в O(n^2), а третий вложенный l oop в O(n^2) тоже.

Таким образом, общий алгоритм будет выполняться в O(n^4).

Однако обратите внимание, что на практике такой случай должен быть довольно редким, и алгоритм должен работать намного быстрее на случайных входах с множеством разных чисел. Сложность, вероятно, может быть улучшена до O(n^3) или даже O(n^2), если этот критический случай исправлен (например, путем отдельного вычисления этого патологического случая).

...