iT邦幫忙

2019 iT 邦幫忙鐵人賽

DAY 2
0
自我挑戰組

競技程式設計的藝術系列 第 2

效率與思維_(:3 」∠ )_

演算法的效率

在解題時給定輸入規模時常大的許多,一些 2 倍 3 倍 甚至 10 倍的優化其實不在演算法競賽時考慮的要點。
我們所設計的演算法必須根據輸入規模而定。

  • Big O 表示法
    https://ithelp.ithome.com.tw/upload/images/20181016/20107376ZWcu9Wxyn2.png
    通俗的說,當 N 足夠大的時候,我們存在一正數 c 使得 c|g(N)| 大於等於 |f(N)|

例如: f(x)= x^2 + x + 1 在 x 很大的時候,主要影響整個函數值的大小是平方項,這時我們可以說 f(x) = O(x^2)

假設輸入規模為 N,常見的複雜度有:
https://ithelp.ithome.com.tw/upload/images/20181016/201073762X8uEUugsP.png

設計演算法的思維

這邊探討幾個常見去設計一個演算法的切入點

考慮最大連續和問題:
給定一個長度為 N 的整數數列 A[1], A[2], .. , A[n],要求找到 1 <= i <= j <= n,使得 A[i] + A[i+1] + .. + A[j] 儘量大。

枚舉

所謂枚舉,通俗點說就是數出部份給定的集合中元素。
下面直接給出程式來解決最大連續和問題:

int best = A[1]; //與其用 int 最小值,不如這樣初始化更不易出錯

for (int i = 1; i <= N; i++)
  for (int j = i; j <= N; j++) {
    int sum = 0;
    for (int k = i; k <= j; k++) sum += A[k];
    best = max(best, sum);
  }

粗估一下可知道複雜度為 O(N^3)

練習:
GCJ Kickstart Round G 2018 A Product Triplets: Small dataset

動態規劃

部份朋友可能知道可以令 S[i] = A[1] + A[2] + ... A[i]
而 A[i] + A[i+1] + ... + A[j] = S[j] - S[i-1]
這樣子有了 S[i] 就可將連續和的計算從 O(N) 降為 O(1)

構造 S[i] 非常的直覺:

S[0] = 0;
for (int i = 1; i < N; i++) S[i] = S[i-1] + A[i];

從邊界遞推地紀錄所有問題的解,且一個項用到前一項的最佳結果,就是動態規劃的精神。

而程式可改進為:

for (int i = 1; i <= N; i++)
  for (int j = i; j <= N; j++) best = max(best, S[j] - S[i-1]);

複雜度降為 O(N^2)。

練習:
CODEFORCES 1033C Permutation Game

貪心法

貪心籠統的講,就是在做決策時,看到它可能是解,就認為它是解。
貪心法其實是動態規劃的特例,上面動態規劃恰好可以用貪心的角度去看,
即 每次 S[i] 所遞推拿的項 A[i],正好不用任何考慮,疊上 S[i-1] 它就是解。

練習:
ZEROJUDGE d652 貪婪之糊
CODEFORCES 1065C Make It Equal

分治法

分治 (divide & conquer) 簡稱 D&C,就是將一個大的問題,分成幾個互相獨立的子問題,然後再將子問題分成子子問題,一直重複分割的動作,直到最小的問題足夠和別的最小問題合併求解出父問題。

將數列切一半,問左半的以及右半的最大連續和多少,以及問包含切開的那道分水嶺的最大連續和為多少,選出三者中最大值,它就是整個數列(原問題)的最大連續和:

int maxsum(int l, int r) {
  if (r-l == 1) return A[l];

  int m = (r+l)/2, sum, centre = A[m];

  sum = 0;
  for (int i = m  ; i <  r; i++) centre = max(centre, sum += A[i]);
  sum = centre;
  for (int i = m-1; i >= l; i--) centre = max(centre, sum += A[i]);

  return max(centre, max(maxsum(l, m), maxsum(m, r)));
}

其複雜度為 O(NlgN)
要驗證分治法的正確性,只需考慮子問題們解完後(假設已拿到解),再合併為父問題看是否解完即可,還要考慮最小的孫子問題到的邊界是否正確。

今天先這樣,明天見!


上一篇
動機 (ゝ∀・)
下一篇
存資料 (゚д゚)
系列文
競技程式設計的藝術8

尚未有邦友留言

立即登入留言