推 mi981027: 57 b 任何flow的流量|f| 一定小於等於任何cut的容量c(S, 12/30 19:41
→ mi981027: T) 12/30 19:41
→ mi981027: 所以若有flow的流量剛好等於某個cut的容量 他一定是max 12/30 19:41
→ mi981027: flow 12/30 19:41
→ mi981027: c 他的意思是flow的流量會被多少cut set bounded 我的想 12/30 19:41
→ mi981027: 法是 12/30 19:41
→ mi981027: cut set的定義必須分開s跟t，那假設有n個點，扣掉s, t 12/30 19:44
→ mi981027: 剩n-2個點 12/30 19:44
→ mi981027: 每個點都可以選擇要分在S或T 總共的分法是2^{n-2}種 12/30 19:44
→ mi981027: 所以應該是O(2^n)?? 12/30 19:44
推 mi981027: loop invariant應該要解釋成：某個statement 不論loop 12/30 20:01
→ mi981027: 執行到什麼階段 這個statement都為真 這樣會比較好理解 12/30 20:01
→ mi981027: 其實這邊他就是要考輾轉相除法的原理是什麼 12/30 20:01
→ mi981027: 也就是gcd(m,n) = gcd(n,r) 12/30 20:01
→ mi981027: 對應到42就是A選項 因為這是一個定理 所以不論loop到什 12/30 20:01
→ mi981027: 麼階段、m, n的值是什麼 都不會改變這個statement的正確 12/30 20:01
→ mi981027: 性 所以他是這裡的loop invariant 12/30 20:01
→ mi981027: loop invariant可以用來驗證algorithm的正確性 可以這 12/30 20:01
→ mi981027: 樣驗證 12/30 20:01
推 plsmaop: CLRS 第一章還是第二章有解釋什麼是 loop invariant 12/31 07:53