推广一个简单的线性时间算法

我想写一个线性时间算法O（n），它给出一个表A [0..n-1] （用自然数递增）检查是否存在是满足f（A [i]，A [j]）= C （C是预定义的常数）的对A [i]，A [j]。推广一个简单的线性时间算法

假设F（A，B）= A + B的算法是：

Algo Paires(A[0..N-1], C) 
in: Tab A[0..n-1] and C a constant 
out : Boolean 
Init indice ← 0 
For i ← 0..n-1 do 
    if indice ≠ i & A[indice] + A[i] = C 
     return true 
    else if i = n-1 & indice ≤ n-2 
     indice++; i ← 0; 
End for 
return False

但如果：

enter image description here

会是怎样的算法呢？有什么建议么？

来源

2011-03-14 Mooh

这听起来像你希望我们做的功课你。 – 2011-03-14 19:16:37

我只是寻找一些帮助，我认为我在正确的地方...我写了算法我自己现在我想概括它，但不幸我不知道如何...我不想你做对我来说，但帮助我一些提示或建议.... – Mooh 2011-03-14 19:26:11

这是O（n²）。 – aaz 2011-03-14 19:32:27

提示：假设有一个二维矩阵，它的行和列进行排序，你给出你需要找到一个数x ...

来源

2011-03-14 19:20:29

似乎我们不再需要寻找线性算法，因为这个答案和示例中的伪代码都是二次的。鉴于此，我们可以在O（1）空间中计算答案吧？ – efficiencyIsBliss 2011-03-15 00:13:49

@efficieny：你为什么认为这是二次方？ – 2011-03-15 00:54:01

@efficiencyIsBliss：正如我上面提到的，尽管伪代码是二次的，但它当然可以在线性时间内完成（所以可以这样做）。 – 2011-03-15 22:47:04

推广一个简单的线性时间算法

回答

相关问题