代码段的时间复杂度是否小于O(n^2)?

Question

我对算法和数据结构不熟悉。因此，我加入了LeetCode来提高我的技能。第一个问题是提出一个时间复杂度小于O(n^2)的算法。我使用了下面的代码片段。

def twoSum(nums: List[int], target: int)->List[int]:
for x in range(len(nums)):
for y in range(x+1, len(nums)):
if nums[x] + nums[y] == target:
return [x, y]
return [0, 0]
nums = [1,2,3,4]
target = 7
twoSum(nums, target)

但在最坏的情况下，它迭代N项(indices ->[0,1,2,3])乘以(N-1)/2次(外部索引:内部索引->0:[1,2,3]， 1:[2,3]， 2:[3])，看起来像O(n^2)。我的推理有什么错误吗?或者在LeetCode上有错误?

Answer 1

这是O(n^2)。你可以很容易地计算出你的解决方案的时间复杂度，这基本上是解决这个问题的蛮力方法。

在最坏的情况下，你有一个[n, n-1，…]， 1]等于n * (n + 1)/2，等于0 (n^2)

请注意，这些平台不能真正计算时间复杂度，他们只是在他们的系统上设置了一个时间限制，这在任何方面都是不准确的。

这个问题有一个简单的解决方案，使用Hashmap，它给你一个O(n)的解决方案，希望你能自己弄清楚。