algorithm - "Merging 2 Packages"问题的大O时间复杂度

Question

在其中一个编码面试准备网站上，我被问到这个问题:

Merging 2 Packages Given a package with a weight limit limit and an array arr of item weights, implement a function getIndicesOfItemWeights that finds two items whose sum of weights equals the weight limit limit. Your function should return a pair [i, j] of the indices of the item weights, ordered such that i > j. If such a pair doesn’t exist, return an empty array.

Analyze the time and space complexities of your solution.

Example:

input: arr = [4, 6, 10, 15, 16], lim = 21

output: [3, 1] # since these are the indices of the # weights 6 and 15 whose sum equals to 21

最初我想的是一个迭代数组的解决方案，然后是一个内部循环来迭代剩余的数组以检查是否存在赞美(limit - elementA = elementB)。

这是我的代码:

def get_indices_of_item_weights(arr, limit):    
    for idx, i in enumerate(arr):
        diff = limit - i          
        if diff in arr[idx+1:]:   # constant lookup
            for idx2, j in enumerate(arr[idx+1:]):
                if j == diff:
                    return [idx+idx2+1, idx]
    return []

该网站解释说，像这样的解决方案仍然是 O(N^2) 时间复杂度。但是，由于剩余数组变小，时间复杂度不会降低吗？即 O(log N)。

有人可以帮助解释为什么这种方法不是 O(log N) 吗？

Answer 1

对于前半部分的每个包，您必须查看所有后半部分的包。那里给出了 (n/2) * (n/2) = n^2/4 = O(n^2) 比较的下限。