arrays - 以下代码的时间复杂度是多少？我很困惑

Question

array = [1,2,4,5]
sum = 3
def arrfilter2(arr):
    for i in arr:
        if ((sum-i) in arr):
            return True
    return False
print(arrfilter2(array))

在此处输入图像描述

标签： arrayspython-3.xalgorithmdata-structurestime-complexity

Answer 1

如果数组未排序，(sum - i) in arr则采用O(n)(n是数组的长度)。在最坏的情况下，循环会扫描所有数组。因此，时间复杂度为O(n^2)。

顺便说一句，在最好的情况下，它可以在O(1).

如果数组已排序，则可以通过二进制搜索技术而不是“in”运算符做得更好。在这种情况下，最坏的情况将是O(n log n)。