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
Nội dung trích xuất từ tài liệu:
Algorithms and Data Structures in C part 6 Table2.2Calculationsfora 100MFLOPmachineTime #ofOperations 1second 108 1minute 6×109 1hour 3.6×1011 1day 8.64×1012 1year 3.1536×1015 1century 3.1536×1017 100trillionyears 3.1536×10292.1.1JustificationofUsingOrderasaComplexityMeasureOne of the major motivations for using Order as a complexity measure is to get a handle on theinductive growth of an algorithm. One must be extremely careful however to understand that thedefinition of Order is “in the limit.” For example, consider the time complexity functions f1 and f2defined in Example 2.6. For these functions the asymptotic behavior is exhibited when n ≥ 1050.Although f1 Θ (en) it has a value of 1 for n < 1050. In a pragmatic sense it would be desirable tohave a problem with time complexity f1 rather than f2. Typically, however, this phenomenon willnot appear and generally one might assume that it is better to have an algorithm which is Θ (1)rather than Θ (en). One should always remember that the constants of order can be significant inreal problems.Example 2.2 OrderExample 2.3 Order Previous TableofContents 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 TableofContents Next 2.2 InductionSimple induction is a two step process: •EstablishtheresultforthecaseN=1 •ShowthatifistrueforthecaseN=nthenitistrueforthecaseN=n+1This 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 theproperty that ifthen either •xyor •x=yExample 2.4 OrderAdditionally, if S′ is a nonempty subset of S:then S′ has a least element. An example of simple induction is shown in Example 2.5.The well-ordering property is required for the inductive property to work. For example considerthe method of infinite descent which uses an inductive type approach. In this method it isrequired to demonstrate that a specific property cannot hold for a positive integer. The approachis as follows:Example 2.5 Induction 1.LetP(k)=TRUEdenotethatapropertyholdsforthevalueofk.AlsoassumethatP(0)does notholdsoP(0)=FALSE. Let S be the set that From the well-ordering principle it is true that if S is not empty then S has a smallest member. Let j be such a member: 2.ProvethatP(j)impliesP(j‐1)andthiswillleadtoacontradictionsinceP(0)isFALSEandjwas assumedtobeminimalsothatSmustbeempty.Thisimpliesthepropertydoesnotholdforany positiveintegerk.SeeProblem2.1forademonstrationofinfinitedescent.2.3 RecursionRecursion is a powerful technique for defining an algorithm.Definition 2.6A procedure is recursive if it is, whether directly or indirectly, defined in terms of itself.2.3.1FactorialOne of the simplest examples of recursion is the factorial function f(n) = n!. This function can bedefined recursively asA simple C++ program implementing the factorial function recursively is shown in Code List2.1. The output of the program is shown in Code List 2.2.Code List 2.1 FactorialCode List 2.2 Output of Program in Code List 2.12.3.2FibonacciNumbersThe Fibonacci sequence, F(n), is defined recursively by the recurrence relationA simple program which implements the Fibonacci sequence recursively is shown in Code List2.3. The output of the program is shown in Code List 2.4.Code List 2.3 Fibonacci Sequence GenerationCode List 2.4 Output of Program in Code List 2.3The recursive implementation need not be the only solution. For instance in looking for a closedsolution to the relation if one assumes the form F (n) = λn one haswhich assuming λ ≠ 0The solution via th ...