tailieunhanh - Algorithms and Data Structures in C part 6

One of the major motivations for using Order as a complexity measure is to get a handle on the inductive growth of an algorithm. One must be extremely careful however to understand that the definition | Table Calculations for a 100 MFLOP machine Time of Operations 1 second 108 1 minute 6x109 1 hour 1 day 1 year 1 century 100 trillion years Justification of Using Order as a Complexity Measure One of the major motivations for using Order as a complexity measure is to get a handle on the inductive growth of an algorithm. One must be extremely careful however to understand that the definition of Order is in the limit. For example consider the time complexity functions f and f2 defined in Example . For these functions the asymptotic behavior is exhibited when n 1050. Although f E 0 en it has a value of 1 for n 1050. In a pragmatic sense it would be desirable to have a problem with time complexity f rather thanf2. Typically however this phenomenon will not appear and generally one might assume that it is better to have an algorithm which is 0 1 rather than 0 en . One should always remember that the constants of order can be significant in real problems. Example Order Example Order Previous Table of Contents Next Copyright CRC Press LLC Algorithms and Data Structures in C by Alan Parker CRC Press CRC Press LLC ISBN 0849371716 Pub Date 08 01 93 Previous Table of Contents Next Induction Simple induction is a two step process Establish the result for the case N 1 Show that if is true for the case N n then it is true for the case N n 1 This will establish the result for all n 1. Induction can be established for any set which is well ordered. A well-ordered set S has the property that if then either x y x y or x y Example Order Additionally if S is a nonempty subset of S then S has a least element. An example of simple induction is shown in Example . The well-ordering property is required for the inductive property to work. For example consider the method of infinite descent which uses an inductive type approach. In this method it is required to demonstrate that a specific property cannot .