我有这个功能,可以从数字列表中创建对。我们知道每次都会有n次选择2次迭代。那么这会使时间复杂度为 O(nC2) 吗? 还是 O(n^2)?
如果是 O(n^2) 为什么是 O(n^2)?该函数不会迭代那么多次,而且永远不会。
def find_pairs(nums):
pairs = []
for i in range(len(nums)):
current = nums[i]
for n in nums[i+1:]:
pairs.append((current, n))
return pairs
以上代码的时间复杂度为
O(n^2)
它总是会迭代 2 次,两次都是在 nums 上,
就在它完成后 current = nums[i]
如果你的 secn 循环不在第一个循环中,它会再次迭代,即像这样的东西
def find_pairs(nums):
pairs = []
for i in range(len(nums)):
current = nums[i]
for n in nums[i+1:]:
pairs.append((current, n))
return pairs
那么时间复杂度就是
O(n)
时间复杂度与算法运行的确切次数无关,而是算法的扩展方式。
在你的情况下,n 选择 2 等于:
n! / (2 * (n - 2)!)
这可以简化为
n * (n-1) / 2 = (n^2 - n) / 2
如您所见,我们有一个二阶多项式函数(二次)。因此,我们认为时间复杂度为
O(n^2)
,因为它将以二次方式缩放。