推 hardcover:感謝分享 01/24 01:58
※ 引述《hardcover (精裝版喔)》之銘言：
: 請問一下
: loop invariant是指什麼?
: 看半天看不懂 XD
: 書上寫得像在講數學歸納法
也是可以這麼說啦 XD
: wikipedia上寫得更神奇
: 到底在講什麼啊?
: thanks
簡單說就是在程式中的loop 如果有某loop invariant LI
嘖每loop一次都可保持滿足LI裡的某種條件(條件不變=>invariant)
當跑完n次loop結束以後 這個條件或是狀態還是會滿足不變式的定義
那個定出來的不變式通常就是我們想要的結果
比如說如果有個迴圈的LI是跑完第i次loop 在陣列a中的前i個element由小到大排好
那這個迴圈跑n次(loop n次) 那陣列中前n個element就小到大排好
如果n等於陣列大小 那陣列就等於是由小到大排序好...
像是bubblesort的loop invariant就可能是跑完第i次loop 前i大的element會被配置
在陣列尾端i個位置尚且由小到大排列好
insertion sort就可能是最上面題的例子...
如果能證明某個loop可達成某LI 就可以證明跑完loop結果會滿足LI裡面的條件定義
所以通常拿來證明某個演算法是否正確 只要能保持某LI直到最後 就可證明是正確的
所以說像是數學歸納法應該是因為拿來證明了吧? 證明第n步對 n+1也對 所以blahblah
-----
有錯請指正~ 謝謝 :p
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.115.217.14
※ 編輯: cplusplus 來自: 140.115.217.14 (01/23 12:22)