“合并两个包”问题的大O时间复杂度

Question

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

将具有权重限制的包和项权重数组合并为2个包，实现一个函数getIndicesOfItemWeights，该函数查找权重之和等于权重限制的两个项。您的函数应该返回项目权重索引的对i，j，排序为i>j。如果不存在，则返回一个空数组。 分析解决方案的时间和空间复杂性。 示例： 输入: arr = 4、6、10、15、16、lim = 21 输出: 3，1#，因为这是#权重6和15的指数，其和等于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 )吗？

Answer 1

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

Answer 2

你是枚举所有对( i，j)，其中j>i，有N*N个数(i，j)，没有任何限制。减去(i，i)我们有N*N-N数。现在每对发生的精确两倍，例如(1,2)和(2,1)，除以2，找到所有对(i，j)的数目，其中k>i，as (N*N - N) /2，仍然是O(N*2)。

检查N=4 expect (4*4-4)/2=6

1,2 1,3 1,4

2,3，2,4

3,4

Answer 3

数组的排序是O(n log )。使用排序数组寻找合适的对是O(n)，从排序数组的末端向内行走可以找到这种情况。从(1，n)开始，然后，对于每对(j，i)，加上j< i:除非找到了目标，或者没有找到目标，并且i =j+ 1，否则如果和小于目标，将一个加到j，然后重复，否则和大于目标，从i中加减一个，然后重复。时间要么是O(n log )，要么是O( n)，这取决于数组最初是否被排序。所需空间取决于排序算法。在排序数组上找到对具有常量存储。