任务算法

Question

我正在尝试降低这个循环的复杂性，这是我的代码

def find_indexes(array, size, value):
    list_indexes = []
    for i in range(size):
        for j in range(size):
            if (array[i] + array[j] == value and i != j):
                list_indexes.append([i, j])
    return list_indexes

array = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
find_indexes(array, len(array), 12)

输出显示“[[0, 8], [1, 7], [2, 6], [3, 5], [5, 3], [6, 2], [7, 1 ], [8, 0]]" 这是正确的

但是这个解决方案有时间复杂度（N^2），这可以在 O(N) 和 O(NLgN) 中完成吗？请为此提出一个algorithm/code/psuedo-code。

该程序基本上是将每个值与其他每个值进行比较，将两个值相加并与 x 进行比较。如果它等于 x。它将它附加到列表中。

数组始终按降序排列。我们必须找到“[array[i] + array[j] == value，其中 i 和 j 是数组的两个独立索引]”

O(N) 中的解决方案

import math
array = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
size = len(array)
X = 12

def Q1_1_N(array, size, value):
    list_indexes = []

    i, j = 0, size - 1
    while (i <= j):
        j = size - 1
        while(j != int((size / 2) - 1)):
            if array[i] + array[j] == value:
                list_indexes.append([i, j])
            j -= 1
        i += 1

    return list_indexes


result = Q1_1_N(array, size, X)
print("Array :", array, "\nX :", X)
if result == []:
    print([-1, -1])
else:
    print("Result Indexes :", result)

输出：

数组：[10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

X : 12

结果索引：[[0, 8], [1, 7], [2, 6], [3, 5]]

Answer 1

由于数组总是按降序排列，您可以通过从两端扫描数组来做到这一点。像这样

p1 = 0
p2 = array.size -1
while p1 < p2
   let v = array[p1] + array[p2]
   while v < value
      if v = value then
          result.append(p1,p2)
          break -- exit the while loop
       p2--
       let v = array[p1] + array[p2]
   p1++

当指针满足您的要求时，您将只生成您已经找到的对的镜像。

如果 v 变得大于值，则 p1 指向的数字不存在一对。

任务算法

Algorithm For Task

python

algorithm

analysis