算法分析与设计ALgoDALectureNotesW1章节.pptVIP

Example Lower bound: To establish a lower bound we may assume that the entries in the list are all distinct. This assumption is permissible because if we can establish a lower bound on worst-case behavior for some subset of inputs (lists with distinct entries), it is a lower bound on worst-case behavior when all valid inputs are considered. Example In a list with n distinct entries, n – 1 entries are not the maximum. We can conclude that a particular entry is not the maximum only if it is smaller than at least one other entry in the list. Hence, n – 1 entries must be “losers” in comparisons done by the algorithm. Each comparison has only one loser, so at least n – 1 comparisons must be done, Thus F (n) = n – 1 is a lower bound on the number of comparisons needed. Conclusion: Algorithm FINDMAX is optimal. How ? Complete Development of an Algo. 1 Statement of the problem 2 Development of a Model 3 Design of the algorithm 4 Correctness of the algorithm 5 Implementation 6 Analysis and complexity of the algorithm 7 Program testing 8 Documentation Statement of the problem Before we can understand a problem, We must be able to give it a precise statement. This condition is not, in itself, sufficient for understanding a problem, but it is absolutely necessary. Developing a precise problem statement is usually a matter of asking the right questions. Some good questions to ask upon encountering a crudely formulated problem are: Statement of the problem Do I understand the vocabulary used in the raw formulation? What information has been given? What do I want to find out? How would I recognize a solution? What information is missing, and will any of this information be of use? Is any of the given information worthless? What assumptions have been made? Development of a Model Once a problem has been clearly stated, it is time to formulate it as a mathematical model. This is a very important step in the overall solution process and it should be given cons