这个算法对于两个数组的时间复杂度是多少？

Question

下面代码的时间复杂度是多少？

import math
arr1 = [2,3,5,6]
arr2 = [1,4,7,8,9,10,21]

for i in range(len(arr2)):
    #some operations

for i in range(len(arr1)):
    for j in range(2,int(math.sqrt(arr1[i]))):
        #some operations

O(n+m*q)（其中 n 是 arr2 的大小，m 是 arr1 的大小）是否正确？我可以简化一下吗？我只是想知道当我们搜索数组中的所有元素然后计算另一个数组中的所有元素时的复杂度是 sqr(n) 运算。

Answer 1

O(n + m * sqrt(k))

，其中：

• n

  是

  arr2

  的长度；

• m

  是

  arr1

  的长度；

• k

  是

  arr1

  中的最大数。

sqrt(k)

与

k**1/2

相同，因此它是次线性的，因此不能简化为

k

。

您可能会在 Computer Science Stack Exchange 中找到更完整的答案。