Introduction to Computers and Programming Prof. I. K. Lundqvist Lecture 9 April 7 2004 So far … • Data structures • Algorithms“Just how good is my algorithm?”3 Complexity Analysis Time (seconds) 60 50 40 30 20 10 0 1 2 3 4 5 O(C) O(n2) “Just how good is my algorithm?” 4 In-class Exercise and calculates the sum of all integers 1..N • Best case vs. worst case • Storage vs. Computation time • Computing the computation time • Big-O notation • Write a procedure that reads an integer N5 Code Comparison linear time? with Ada.Integer_Text_Io, Ada.Text_Io;use Ada.Integer_Text_Io, Ada.Text_Io; procedure CalcSum is N : Integer;Total_Sum : Integer;beginPut_Line("Enter an Integer: ");Get(N);Total_Sum := 0;for I in 1..N loopTotal_Sum := Total_Sum + I;;Put(Total_Sum);end; 6 Code Comparison with Ada.Integer_Text_Io, Ada.Text_Io;use Ada.Integer_Text_Io, Ada.Text_Io; procedure Calcsum is N : Integer;Total_Sum : Integer; beginPut_Line("Enter an Integer: ");Get(N);Total_Sum := 0;Total_Sum := (N * (N + 1)) / 2;Put(Total_Sum);end; N*(N+1) 2 • How many have a solution that runs in end loop• How many have a solution that runs in constant time?7 Complexity Analysis : rate at which storage or time grows as a function of the problem size : describes the inherent complexity of a program, independent of machine and compiler – Ideacan be described as a simple proportionality to some known function. 8 Common Notations for Big-O M) N) Or a combination of these constant time or space •Complexity– Growth depends on compiler, machine, … • Asymptotic analysis: as problem size grows, the complexity •O(1) •O(N) •O(log N) •O(N•O(M9 O(1) of what input we give to the algorithm • • •… 10 O(N) elements to find that the element we are looking for does not exist • does not exist • size N where a value does not exist • Constant time or space, independently •Examples: Access element in an array Retrieve the first element in a list • We have to search through all existing •Examples: Searching for element in a list that Searching through a Binary Tree of11 O(log N) • • search • into O(log N) 12 Binary Search How many elements are examined in worst case? 10 11 14 17 21 33 55 6257 71 87 89 91 93 95 97 1 2 3 4 5 6 7 98 Example, a full balanced Binary Search Tree Can eliminate half of the BST every time the Any algorithm that eliminates a large portion of the data set at each iteration is generalized 10111213141516•Ex?13 Binary Search Input:Array to search, element to search forOutput:Index if element found, -1 otherwiseAlgorithm:Set Return_Index to -1;Set Current_Index to (UB + LB) /2 Loopif the LB > UB Exit; Return_Index := Current_IndexExit; LB := Current_Index +1else Return Return_Index 14 O(NM) N := 1;while N > 0 loopPut( );Get(N);X := 0; for I1 in 1..N loopfor I2 in 1..N loopfor I3 in 1..N loopfor I4 in 1..N loopfor I5 in 1..N loopX := X + 1; ; ; ; ; ;Put(X);New_Line; ; if Input_Array(Current_Index) = elementif Input_Array(Current_Index) < element UB := Current_Index - 1 "How many repetions? "end loopend loopend loopend loopend loopend loop15 O(MN) – f(0) = 1 – f(1) = 1 – f(n+2) = f(n) + f(n+1) ∀ n≥0 2N calculations 16 Big-O 1 and largest N2 number in a list and generate a new list of 1 and N2 • Example: Fibonacci algorithm •O(N+M) – Sequential and unrelated tasks – Ex: to find the smallest Nall the numbers in between N•O(N*M) –Nesting of tasks – Ex: initializing a n-by-m matrix17 Asymptotic Analysis: Big-O Definition:T(n) = O(f(n)) – “T of n is in Big-Oh of f of n” c and n0 such that: T(n) ≤ cf(n) for all n ≥ n0 : The algorithm is in O(n2) in [best, average, worst] case. Meaning: For all data sets big enough (i.e., n>n0), the algorithm always executes in less than cf(ncase. Big-O is said to describe an “upper bound18 Big-O Examples Finding value X in an array (average cost). T(n) = csn/2. For all values of n > 1, csn/2 <= csn. Therefore, by the definition, T(n) is in O(n) for n0 = 1 and c = cs. T(n) = O(f(n)) iff T(n) ≤ cf(n) for all n ≥ n0 • Mathematical concept that expresses “how good” or “how bad” an algorithm is iff there are constants Usage) steps in [best, average, worst] ”on the complexity.19 Big-O Example T(n) = c1n2 + c2n in average case. c1n2 + c2n <= c1n2 + c2n2 <= (c1 + c2)n2 for all n > 1. T(n) <= cn2 for c = c1 + c2 and n0 = 1. Therefore, T(n) is in O(n2) by the definition T(n) = O(f(n)) iff T(n) ≤ cf(n) for all n ≥ n0 Big-O Simplifications O(2*N) Same as O(N) O(5*3N) Same as O(3N) O(4711) Same as O(1) O(N+1) Reduces to O(N) O(N2+logN) Reduces to O(N2) O(N*logN+2N+50000) Reduces to O(2N) 2021 Big-O Simplifications Same asO(N*M+N2) Same asO(N2logP+N) Reduces toO(5*N3 Same asO(N+P+Q) O(N+P+Q) O(5*N3+2P+Q*R) O(N2logP+N) O(N*M+N2) 22 Faster Computer or Algorithm? The old computer processes 10,000 instructions per hour What happens when we buy a computer 10 times faster? -----16132n 3.16223702n2 7.371,8422505n log n 105,00050020n 1010,0001,00010n n’/nn’nT(n) + 7N+
View Full Document
Unlocking...