notasi big o

21
Notasi Big O

Upload: juitha-asry

Post on 08-Oct-2015

11 views

Category:

Documents


0 download

TRANSCRIPT

Notasi Big O

Notasi Big OPermasalahan (latihan)Badu menemukan peti harta karunUtk membukanya diperlukan PIN 4 digitPIN-nya adalah 4 digit terakhir dari 9 pangkat N

Solusi 19 pangkat 10 = kira2 10 digitTidak muat dalam tipe data intHanya perlu 4 digit terakhir123456789 : 4 digit terakhir = 6789How to get?123456789 mod 10000 = 6789Solusi 1int N= ____;int i, pin=1;for(i=0;i1;}printf(pin=%d\n, pin);Which one better?Solusi 1Berjalan N loopSolusi 2Berjalan 6 loop6 = jml digit utk menyimpan angka 100 (max N)

Teori ttg Notasi Big OAnalysis of Algorithms9 Analysis of Algorithms Estimate the running timeEstimate the memory space required.

Time and space depend on the input size.

Analysis of Algorithms10Running Time (3.1) Most algorithms transform input objects into output objects.The running time of an algorithm typically grows with the input size.Average case time is often difficult to determine.We focus on the worst case running time.Easier to analyzeCrucial to applications such as games, finance and robotics

Analysis of Algorithms11Experimental StudiesWrite a program implementing the algorithmRun the program with inputs of varying size and compositionUse a method like System.currentTimeMillis() to get an accurate measure of the actual running timePlot the results

Analysis of Algorithms12Limitations of ExperimentsIt is necessary to implement the algorithm, which may be difficultResults may not be indicative of the running time on other inputs not included in the experiment. In order to compare two algorithms, the same hardware and software environments must be used

Analysis of Algorithms13Theoretical AnalysisUses a high-level description of the algorithm instead of an implementationCharacterizes running time as a function of the input size, n.Takes into account all possible inputsAllows us to evaluate the speed of an algorithm independent of the hardware/software environment

Analysis of Algorithms14Pseudocode (3.2)High-level description of an algorithmMore structured than English proseLess detailed than a programPreferred notation for describing algorithmsHides program design issuesAlgorithm arrayMax(A, n)Input array A of n integersOutput maximum element of AcurrentMax A[0]for i 1 to n 1 doif A[i] currentMax thencurrentMax A[i]return currentMax Example: find max element of an arrayAnalysis of Algorithms15Pseudocode DetailsControl flowif then [else ]while do repeat until for do Indentation replaces braces Method declarationAlgorithm method (arg [, arg])Input Output ExpressionsAssignment(like in Java)Equality testing(like in Java)n2Superscripts and other mathematical formatting allowed

Analysis of Algorithms16Primitive Operations (time unit)Basic computations performed by an algorithmIdentifiable in pseudocodeLargely independent from the programming languageExact definition not important (we will see why later)Assumed to take a constant amount of time in the RAM modelExamples:Evaluating an expressionAssigning a value to a variableIndexing into an arrayCalling a methodReturning from a methodComparison x==y x>Y

Analysis of Algorithms17Counting Primitive Operations (3.4)By inspecting the pseudocode, we can determine the maximum number of primitive operations executed by an algorithm, as a function of the input sizeAlgorithm arrayMax(A, n) # operationscurrentMax A[0] 2for (i =1; i