更快的算法

我被告知要編寫如下算法有三個數組A []，B []，C []具有相同的大小N.找出所有可能的（i，j，k），使得A [1] + B [j]的= C [k]的。最大允許時間複雜度爲O（N^2）。繼是我爲輸出編寫的算法（N^2）更快的算法

#include<stdio.h> 

#define MAX 1000 

struct sum 
{ 
     int result; 
     int i; 
     int j; 
}; 

int main() 
{ 
     struct sum sum_array[MAX]; 
     int n=4; 
     int a[] = {4,1,2,5}; 
     int b[] = {1,7,6,0}; 
     int c[] = {11,3,8,2}; 
     int k; 
     int i,j; 
     for(i=0;i<MAX;i++) 
       sum_array[i].result=-1; 
     for(i=0;i<n;i++) 
     { 
       for(j=0;j<n;j++) 
       { 
         sum_array[a[i]+b[j]].result=a[i]+b[j]; 
         sum_array[a[i]+b[j]].i=i; 
         sum_array[a[i]+b[j]].j=j; 
       } 
     } 
     for(k=0;k<n;k++) 
     { 
       if(sum_array[c[k]].result==c[k]) 
       { 
         printf("<i,j,k> = <%d,%d,%d>\n",sum_array[c[k]].i,sum_array[c[k]].j,k); 
       } 
     } 
     return 0; 
}

我的問題是怎麼做的更快呢？任何O（N * logN）或更好的算法呢？

問候，阿爾卡

來源

2012-04-06 Arka Sharma

您是否在尋找所有可能的（i，j，k）？或者你只是想找到一個三重？你的數組數據是不同的？ – 2012-04-06 13:42:27

您的代碼找不到*全部*組合。如果有多於一對的{i，j}給出相同的總和，那麼你只能捕獲其中的一個。 – 2012-04-06 13:43:00

另外你目前的解決方案是完全錯誤的。它有太多的錯誤。 – 2012-04-06 13:50:41

我不認爲你會發現什麼爲O快（N ），僅僅是因爲你通過所有A的有環路每個B獲得的款項所有的數組元素。這就是O（N ），阻止你獲得更快的速度。

編輯：雖然，有一些優化工作要做。例如，您設置了sum_array[a[i]+b[j]].result = a[i]+b[j]。稍後您測試密鑰是否與結果相同。它怎麼可能是平等的？

來源

2012-04-06 13:42:56

最大的答案是大小N^3，因此沒有更好的複雜性可以實現。以此爲例A = {1,1,1,1,1,1,1}，B = {1,1,1,1,1,1} C = {2,2,2,2,2， 2}你的方法不會爲上面的例子輸出所有可能的三元組。

來源

2012-04-06 13:43:30

+1：簡單的答案。（除非存在某種約束，否則這是正確的，例如每個數組中的元素必須是唯一的。） – 2012-04-06 13:44:22

即使存在所有元素都不相同的約束，也有一個示例，其中答案的大小爲O（N^2 ）：a = {1,2,3，...，n}，b = {1,2,3，...，n} c = {1,2,3，...，n} – 2012-04-06 14:05:13

如果你正在尋找一個組合或只是數這樣的組合則：

讓MAX從陣列A，B，C最大元素。我的解決方案是O(MAX log(MAX))。

我只是在描述沒有細節的想法。

讓A_count[x] =元素數x在數組A。
計算A，B和C這樣的數組。
它可以在線性時間完成。

將陣列A_count，B_count和C_count視爲多項式。如果存在的A[i] + B[j]與X相加，那麼A_count * B_count（乘以多項式）具有coefficient[X]！= 0.

所以現在想法很簡單。計算A_count * B_count並將它們的係數與C_count的係數進行比較。計算A_count * B_count可以在O(MAX log(MAX))中使用Discrete Fourier transform完成。

@edit，例如在

int A[] = {4,1,2}; 
int B[] = {1,0}; 
int C[] = {3,8,2};

讓計算A_COUNT，B_count，C_count

    0, 1, 2, 3, 4, 5, 6, 7, 8 
int A_count[] = {0, 1, 1, 0, 1}; 
int B_count[] = {1, 1}; 
int C_count[] = {0, 0, 1, 1, 0, 0, 0, 0, 1}

現在讓我們來計算A_COUNT * B_count。簡單的乘法算法：

for(int i=0; i<A_count_SIZE; i++) 
    for(int j=0; j<B_count_SIZE; j++) 
     mult_result[i+j] += A_count[i] * B_count[j];

但它可以做得更快（通過Discrete Fourier transform）。

int mult_result[] = {0, 1, 2, 1, 1, 1}

這意味着：

1 pair sums to 1 
2 pairs sums to 2 
1 pair sums to 3 
1 pair sums to 4 
1 pair sums to 5

來源

2012-04-06 14:08:14

我不太明白這種方法。你能提供一個例子嗎？（無論是代碼還是手工計算）。 – 2012-04-06 15:36:48

我已經更新了我的答案。你能告訴我哪一部分你不明白嗎？ – 2012-04-06 17:08:12

這不會告訴你元組是什麼。 – 2012-04-07 15:29:52

如果你想找到三胞胎（I，J，K）的存在，使得A[i]+B[j]=C[k]，那麼就可以在O(n^2 logn)完成。此外，您可以通過使用此方法找到此三元組的計數。

使一個新的數組D[]，使得D保持每一個可能的對A和B的總和。這將使D = n^2的大小。
對數組C排序現在，binary search對於D在數組C中的所有值。時間複雜度爲O(n^2 logn)。

要計算的三元組數，

查找的C[]值lower bound和upper bound在D僅當在D存在值（其可以使用由下界函數返回的索引被選中）。

count + = upper_bound_index - lower_bound_index;

這個的時間複雜度也是O(n^2 logn)。

來源

2012-04-06 18:05:58

回答

相關問題