两和问题的时间复杂度是多少?
what is the Time complexity of of two sum problem?
我正在练习我的 Big O 表示法,需要一些说明。
这是我从 Leet 代码 Two sums problem 中得到的解决方案。基本上给定一个列表和一个目标值,return 两个索引加起来就是目标。
例如
twoSum([1,2,3,4],7)
会 return [2,3]
我在leetcode上看到了解法,但是我想看看我对这段代码的评价是否正确。时间复杂度 = O(n 平方),因为在外循环中对数组进行 in 操作。
这是正确的吗?
密码是
def twoSum_n2(nums, target):
for idx, value in enumerate(nums): #O(n)
diff = target - value # O(1)
try:
diff_idx = nums.index(diff) #O(n)
except ValueError as ex:
continue
if idx != diff_idx: # O(1)
return [idx, diff_idx] #O(1)
return []
是的,在您当前的实现中它是 O(n^2),因为您在另一个 O(n) 中有一个 O(n)。当我们遇到类似情况时,我们需要将这些 O-s 的值相乘。
diff_idx = nums.index(diff) #O(n)
上面的行将被 运行 n 次,因为它在遍历 nums 列表的 for 循环中。因此,检查的总次数为 O(n^2) 次,复杂度为 O(n^2)。
我正在练习我的 Big O 表示法,需要一些说明。 这是我从 Leet 代码 Two sums problem 中得到的解决方案。基本上给定一个列表和一个目标值,return 两个索引加起来就是目标。 例如
twoSum([1,2,3,4],7)
会 return [2,3]
我在leetcode上看到了解法,但是我想看看我对这段代码的评价是否正确。时间复杂度 = O(n 平方),因为在外循环中对数组进行 in 操作。 这是正确的吗?
密码是
def twoSum_n2(nums, target):
for idx, value in enumerate(nums): #O(n)
diff = target - value # O(1)
try:
diff_idx = nums.index(diff) #O(n)
except ValueError as ex:
continue
if idx != diff_idx: # O(1)
return [idx, diff_idx] #O(1)
return []
是的,在您当前的实现中它是 O(n^2),因为您在另一个 O(n) 中有一个 O(n)。当我们遇到类似情况时,我们需要将这些 O-s 的值相乘。
diff_idx = nums.index(diff) #O(n)
上面的行将被 运行 n 次,因为它在遍历 nums 列表的 for 循环中。因此,检查的总次数为 O(n^2) 次,复杂度为 O(n^2)。