introduction_to_algorithms.txt (1012B)
1 ======================================================================== 2 Introduction to Algorithms 3 ======================================================================== 4 5 Loop Invariant 6 7 Loop invariant help up understand why an algorithm is correct. When you're 8 using a loop invariant, you need to show three things: 9 10 - Initialization: If it is true prior to the first iteration of the loop. 11 12 - Maintenance: If it is true before an iteration of the loop, it remains 13 true before the next iteration. 14 15 - Termination: The loop terminates, and when it terminates, the invariant, 16 usually along with the reason that the loop terminated, gives us a useful 17 property that helps show that the algorithm is correct. 18 19 A loop-invariant proof is a form of mathematical induction, where to prove 20 that a property holds, you prove a base case and an inductive step. 21 22 Example: 23 24 Loop invariant of a sum array: 25 26 SUM-ARRAY (A,n) 27 sum = 0 28 for i = 1 to n 29 sum = sum + A[i] 30 return sum 31 32 i-1 33 Σ k 34 k=1 35 36 or 37 38 Σ(k = 1 to i-1) k 39