Является ли временная сложность этого кода O (n ^ 2)? - PullRequest
Новая
       4

Является ли временная сложность этого кода O (n ^ 2)?

0 голосов
/ 20 мая 2019

Проблема находит два элемента в массиве, которые складываются в целевое значение.Он возвращает массив с индексом правильных значений.

Я думаю, что временная сложность равна n ^ 2, потому что цикл while проходит через массив один раз, так что n раз.И в худшем случае он должен повторить это n раз.Так что n * n время работы.

Несмотря на то, что число элементов, через которые он должен проходить, уменьшается с каждым разом, мы пропускаем константы при вычислении.сложность времени.

Является ли этот анализ правильным?Любые рекомендации для того, чтобы понизить это до? 

def twoSum(nums, target):

    indx = []
    size = len(nums)

    if (size < 2):
        return indx

    x = 0
    y = size - 1

    while(x < y):

        if( (nums[x] + nums[y]) == target):
            indx[0] = x
            indx[1] = y
            break
        elif ( (y - 1) == x):
            x = x + 1
            y = size - 1
        else:
            y = y -1

    return indx

1 Ответ

3 голосов
/ 20 мая 2019

Вы можете сделать O(n), это вопрос об интервью Google, у которого есть видео на YouTube, как мне кажется. Или, по крайней мере, у них была очень похожая проблема: 

def twoSum(nums, target):
    values = dict()
    for index, n in enumerate(nums):
        if target - n in values:
            return values[target - n], index
        else:
            values[n] = index


print(twoSum([4, 5, 2, 1, 3], 4)) # (3, 4)

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

...