这段代码的时间复杂度是 O(n^2) 吗? [英] Is the time complexity of this code O(n^2)?

问题描述

该问题在数组中查找加起来为目标值的两项.它返回一个带有正确值索引的数组.

The problem finds two items in the array that add up to target value. It returns an array w/ the index of the correct values.

我认为时间复杂度是 n^2，因为 while 循环遍历数组一次所以 n 次.在最坏的情况下，它必须重复 n 次.所以 n*n 运行时间.

I think the time complexity is n^2 because the while loop runs through array once so n time. And in the worst case, it has to repeat this n times. So n*n running time.

即使每次必须迭代的元素数量都会减少，但我们在 calc 时删除了常量.时间复杂度.

Even though the number of elements it has to iterate through decreases each time, we drop the constants when calc. time complexity.

这个分析正确吗?有没有建议将其降低到 n?

Is this analysis correct? Any recommendations for bringing it down to 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

推荐答案

You can do O(n)，这是一个谷歌面试问题，他们在 YouTube 上有一个视频，我相信.或者至少他们有一个非常相似的问题:

You can do O(n), this is a google interview question that they have a video on YouTube for I believe. Or at least they had a very similar problem:

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 时间(特别是如果给你的测试集试图针对哈希冲突).

- Edit -
Per the comments below, this solution technically still has a worst case of O(n^2) do to hash collisions. For most cases you should get close to O(n) but if you are working with large numbers (negative or positive) you will see an increase in collisions which will result n * log(n) to n^2 time (especially if the test set given to you tries to target hash collisions).

这篇关于这段代码的时间复杂度是 O(n^2) 吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！