loop invariant for Iterative algorithm {make progress: i-1 --> i?}-白红宇

loop invariant for Iterative algorithm {make progress: i-1 --> i?}

阅读量：4963 次

发布时间：2019-06-12

本文共 3388 字，大约阅读时间需要 11 分钟。

Repetition is an opportunity.

Reconsidering Simple Examples

A good martial arts student will attentively repeat each fundamental technique many times.

In contrast, many college students tune out when a concept (eg. depth first search) is taught more than once.

The better students listen carefully in order to refine and develop their understanding.

Designing an algorithm

define problem

define loop invariants

define measure of progress

define step

define exit condition

maintain loop inv

make progress

initial conditions

ending

//insert sort void sort(int a[]){
   for(int i =1;i
     
      0&&a[j-1]>b) a[j]=a[j-1]; j--; } a[j]=b; }

explaining the insertion sort:

If you can't explain what you're doing and why you're doing it to any intelligent layman, that really means that you don't understand it yourself.

By Albeit Einstein.

we maintain a subset of elements sorted within a list.

The remaining elements are off to the side somewhere. Initially, think of the first element in the array as a sorted list of length one. One at a time, we take one of the elements that is off to the side and we insert it into the sorted list where it belongs. This gives a sorted list that is one element longer than it was before. When the last element has been inserted, the array is completely sorted.

state of computation determined by values of all variables.

loop invariant

some subsets of the elements are sorted.

the remaining elements are off to the side.

making the progress while keeping the loop invariant.

running time:

inserting an element into a list of size i takes O(i)

1+2+3+...+n = O(n²)

hope you are beginning to appreciate loop invariants for describing algorithms.

another example

explaining the selection sort

We maintain that the k smallest of elements are sorted in a list. The larger elements are in a set on the side. Initially, with k=0, all the elements are in this set. Progress is made by finding the smallest element in the remaining set of larger elements and adding this selected element at the end of the sorted list of elements. This increases k by one. Stop with k=n. At this point, all the elements have been selected and the list is sorted.

Design algorithm

don't start coding, you must design a working algorithm first.

try solving the problem on small input examples

what basic steps might you follow to make some kind of progress towards the answer?

describe or draw a picture of what the data structure might look like after a number of these steps?

Leap into the middle of the algorithm.

What would you like your data structure to look like when you are half done?