2011-07-22 20:26:09Morris
[技巧] 兩陣列元素交換 不是O(n) 是 O(1)
在此, 先給大家看一個範例
int Min1[1000] = {}, Min2[1000] = {}, tmin = 0;
for(a = 0; a < U; a++) {
for(b = a, c = L-(U-a); b <= c; b++) {
Min2[b] = abs(IU[a]-IL[b]) + tmin;
tmin = (tmin < Min1[b]) ? tmin : Min1[b];
}
for(b = a; b <= c; b++)
Min1[b] = Min2[b];
tmin = Min1[a];
}
紅色的部分, 是要將 Min2 的值, 都給 Min1
這樣實在太慢了, 需要跑 a->c
int Min1[1000] = {}, Min2[1000] = {}, tmin = 0;
int *A = Min1, *B = Min2, *C;
for(a = 0; a < U; a++) {
for(b = a, c = L-(U-a); b <= c; b++) {
B[b] = abs(IU[a]-IL[b]) + tmin;
tmin = (tmin < A[b]) ? tmin : A[b];
}
C = A, A = B, B = C;
tmin = A[a];
}
這樣只需要 O(1), 就完成囉
切記交換的時候, 並不是 *C = *A, *A = *B, *B = *A;
以上的使用, 雖然很短, 一眼就可以看完了, 這速度可不容小覷
神犇就別看了又偷笑我, 我寫了那麼久才知道, 可見我多笨
int Min1[1000] = {}, Min2[1000] = {}, tmin = 0;
for(a = 0; a < U; a++) {
for(b = a, c = L-(U-a); b <= c; b++) {
Min2[b] = abs(IU[a]-IL[b]) + tmin;
tmin = (tmin < Min1[b]) ? tmin : Min1[b];
}
for(b = a; b <= c; b++)
Min1[b] = Min2[b];
tmin = Min1[a];
}
紅色的部分, 是要將 Min2 的值, 都給 Min1
這樣實在太慢了, 需要跑 a->c
int Min1[1000] = {}, Min2[1000] = {}, tmin = 0;
int *A = Min1, *B = Min2, *C;
for(a = 0; a < U; a++) {
for(b = a, c = L-(U-a); b <= c; b++) {
B[b] = abs(IU[a]-IL[b]) + tmin;
tmin = (tmin < A[b]) ? tmin : A[b];
}
C = A, A = B, B = C;
tmin = A[a];
}
這樣只需要 O(1), 就完成囉
切記交換的時候, 並不是 *C = *A, *A = *B, *B = *A;
以上的使用, 雖然很短, 一眼就可以看完了, 這速度可不容小覷
神犇就別看了又偷笑我, 我寫了那麼久才知道, 可見我多笨
上一篇：優化輸入的函式
下一篇：Hash table %& 結論