有人能帮我计算出算法的时间复杂度吗？

Question

示例ArrayOne输入：[-1,5,10,20,28,3]

示例阵列两个输入：[26、134、135、15、17]

我猜是O（n^2+m^2），其中n是ArrayOne的长度，m是ArrayTwo的长度

Answer 1

为什么这个代码不写为：

minDiff = float("inf")
for value1 in arrayOne:
    for value2 in arrayTwo:
        minDiff = min(minDiff, abs(value1 - value2))

这段代码似乎在刻意隐藏一个事实，即它是一对嵌套的迭代，其时间是显而易见的

这也意味着它可以用Python写成一行：

minDiff = min(abs(value1 - value2) for value1 in arrayOne for value2 in arrayTwo)

Answer 2

假设len(arrayOne) = n和len(arrayTwo) = m

i = 0 and j = 0

从一开始，您就有一个外部while循环，但它的运行时间并不明显

在while循环中，您执行一些常量工作，然后检查j == m。这是不正确的，因此j增加了m倍

现在j == m，增加i并设置j = -1。这意味着j将再次增加m倍i递增和j重置

j将重置n次

因此，这里的内部循环可以用m表示。通过n和外部循环

因此，该算法的运行时复杂度为O（n*m）