如果我们在 while 循环中有一个 while 循环，我们会增加复杂性吗？（即使使用指针）

Question

下面是一些代码，它包含一个整数列表、nums 和一个目标整数 target，returns nums 中的两个整数加起来就是 target：

def twoSum(nums, target):
    pointer_stat = 0
    pointer_run = 1

    while pointer_stat < len(nums):

        while pointer_run and pointer_stat < len(nums):
            if nums[pointer_stat] + nums[pointer_run] == target:
                return [nums[pointer_run],nums[pointer_stat]]

            pointer_run +=1

        pointer_run = 1
        pointer_stat +=1


print(twoSum(nums,target))

我的问题是，或者更确切地说，我想确认以上是否是 O(n^2) 运行时间？

我的推理是我们有两个指针将指向列表中的每个整数，并且两个指针将分别遍历列表一次（因此复杂度为 O(N)），并且由于我们在内部有一个循环一个循环，我们将 O(N) 和 O(N) 相乘得到 O(N^2)

并且 space 复杂度为 O(1)。

Answer 1

你是对的，但是 O(n^2) 是 最坏情况 时间复杂度，因为你在循环中包含一个 return 语句，这可能导致退出早点双循环。

请注意，您可能需要

while pointer_run < len(nums) and pointer_stat < len(nums):

而不是

while pointer_run and pointer_stat < len(nums):

因为这可能会导致您的循环无法停止（小于比“and”更强的绑定）和运行无限期。

Answer 2

您可以实际测试并亲自查看：

import matplotlib.pyplot as plt
x=[]
y=[]
n=[1]
def twoSum(nums, target):
    pointer_stat = 0
    pointer_run = 1
    iterations = 0

    while pointer_stat < len(nums):

        while pointer_run < len(nums) and pointer_stat < len(nums):
            if nums[pointer_stat] + nums[pointer_run] == target:
                return [nums[pointer_run],nums[pointer_stat]]
            iterations +=1 
            pointer_run +=1

        pointer_run = 1
        pointer_stat +=1
        x.append(len(nums))
        y.append(iterations)
    return True

for i in range(100):
    n.append(1)
    twoSum(n,10000)

plt.plot(x,y)
plt.xlabel('N')
plt.ylabel('Iterations')
plt.show()

如果我们在 while 循环中有一个 while 循环，我们会增加复杂性吗？（即使使用指针）

if we have a while loop inside while loop, do we multiply complexities? (even though pointers are used)

python

time-complexity

如果我们在 while 循环中有一个 while 循环，我们会增加复杂性吗？ （即使使用指针）

if we have a while loop inside while loop, do we multiply complexities? (even though pointers are used)

python

time-complexity

如果我们在 while 循环中有一个 while 循环，我们会增加复杂性吗？（即使使用指针）