Algorithm: a tool for solving a well-defined computational problem (the statement of the problem is the desired input/output relationship)
NP-complete: no known way to determine most efficient algorithm. we settle for reasonable algorithms.
Loop invariant: help us see if an algorithm is correct. Must show that the state is correct at three times:
1. initialization: prior to loop
2. maintenance: at the start of each loop
3. termination: at the termination of the loop
Analyzing an algorithm = predicting the resources it will require
Rate of growth / order of growth = leading term of the running time. eg. insertion sort has an average cost of an2 + bn + c, so we say the running time is theta-n2.
No comments:
Post a Comment