DOC PREVIEW
Penn CIT 594 - Analysis of Algorithms

This preview shows page 1-2-22-23 out of 23 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 23 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 23 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 23 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 23 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 23 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Analysis of AlgorithmsTime and spaceWhat does “size of the input” mean?Characteristic operationsExact valuesHigher-level languagesAverage, best, and worst casesConstant timeLinear timeConstant time is (usually) better than linear timeThe array subset problemmembersubsetAnalysis of array subset algorithmWhat about the constants?Simplifying the formulaeBig O notationBig O for subset algorithmCan we justify Big O notation?y = x2 + 3x + 5, for x=1..10y = x2 + 3x + 5, for x=1..20Common time complexitiesThe EndJan 15, 2019Analysis of Algorithms2Time and spaceTo analyze an algorithm means:developing a formula for predicting how fast an algorithm is, based on the size of the input (time complexity), and/ordeveloping a formula for predicting how much memory an algorithm requires, based on the size of the input (space complexity)Usually ti me is our biggest concernMost algorithms require a fixed amount of space3What does “size of the input” mean?If we are searching an array, the “size” of the input could be the size of the arrayIf we are merging two arrays, the “size” could be the sum of the two array sizesIf we are computing the nth Fibonacci number, or the nth factorial, the “size” is nWe choose the “size” to be a parameter that determines the actual time (or space) requiredIt is usually obvious what this parameter isSometimes we need two or more parameters4Characteristic operationsIn computing time complexity, one good approach is to count characteristic operationsWhat a “characteristic operation” is depends on the particular problemIf searching, it might be comparing two valuesIf sorting an array, it might be: comparing two values swapping the contents of two array locations both of the aboveSometimes we just look at how many times the innermost loop is executed5Exact valuesIt is sometimes possible, in assembly language, to compute exact time and space requirementsWe know exactly how many bytes and how many cycles each machine instruction takesFor a problem with a known sequence of steps (factorial, Fibonacci), we can determine how many instructions of each type are requiredHowever, often the exact sequence of steps cannot be known in advanceThe steps required to sort an array depend on the actual numbers in the array (which we do not know in advance)6Higher-level languagesIn a higher-level language (such as Java), we do not know how long each operation takesWhich is faster, x < 10 or x <= 9 ?We don’t know exactly what the compiler does with thisThe compiler almost certainly optimizes the test anyway (replacing the slower version with the faster one)In a higher-level language we cannot do an exact analysisOur timing analyses will use major oversimplificationsNevertheless, we can get some very useful results7Average, best, and worst casesUsually we would like to find the average time to perform an algorithmHowever,Sometimes the “average” isn’t well definedExample: Sorting an “average” arrayTime typically depends on how out of order the array isHow out of order is the “average” unsorted array? Sometimes finding the average is too difficultOften we have to be satisfied with finding the worst (longest) time requiredSometimes this is even what we want (say, for time-critical operations)The best (fastest) case is seldom of interest8Constant timeConstant time means there is some constant k such that this operation always takes k nanosecondsA Java statement takes constant time if:It does not include a loopIt does not include calling a method whose time is unknown or is not a constantIf a statement involves a choice (if or switch) among operations, each of which takes constant time, we consider the statement to take constant timeThis is consistent with worst-case analysis9Linear timeWe may not be able to predict to the nanosecond how long a Java program will take, but do know some things about timing: for (i = 0, j = 1; i < n; i++) { j = j * i; }This loop takes time k*n + c, for some constants k and c k : How long it takes to go through the loop once (the time for j = j * i, plus loop overhead) n : The number of times through the loop (we can use this as the “size” of the problem) c : The time it takes to initialize the loopThe total time k*n + c is linear in n10Constant time is (usually)better than linear timeSuppose we have two algorithms to solve a task:Algorithm A takes 5000 time unitsAlgorithm B takes 100*n time unitsWhich is better?Clearly, algorithm B is better if our problem size is small, that is, if n < 50Algorithm A is better for larger problems, with n > 50So B is better on small problems that are quick anywayBut A is better for large problems, where it matters moreWe usually care most about very large problemsBut not always!11The array subset problemSuppose you have two sets, represented as unsorted arrays: int[] sub = { 7, 1, 3, 2, 5 };int[] super = { 8, 4, 7, 1, 2, 3, 9 }; and you want to test whether every element of the first set (sub) also occurs in the second set (super): System.out.println(subset(sub, super));(The answer in this case should be false, because sub contains the integer 5, and super doesn’t)We are going to write method subset and compute its time complexity (how fast it is)Let’s start with a helper function, member, to test whether one number is in an array12member static boolean member(int x, int[] a) { int n = a.length; for (int i = 0; i < n; i++) { if (x == a[i]) return true; } return false;}If x is not in a, the loop executes n times, where n = a.lengthThis is the worst caseIf x is in a, the loop executes n/2 times on averageEither way, linear time is required: k*n+c13subsetstatic boolean subset(int[] sub, int[] super) { int m = sub.length; for (int i = 0; i < m; i++) if (!member(sub[i], super) return false; return true;}The loop (and the call to member) will execute:m = sub.length times, if sub is a subset of superThis is the worst case, and therefore the one we are most interested inFewer than sub.length times (but we don’t know how many)We would need to figure this out in order to compute average time complexityThe worst case is a linear number of times through the loopBut the loop body doesn’t take constant time, since it calls member, which takes


View Full Document

Penn CIT 594 - Analysis of Algorithms

Documents in this Course
Trees

Trees

17 pages

Searching

Searching

24 pages

Pruning

Pruning

11 pages

Arrays

Arrays

17 pages

Stacks

Stacks

30 pages

Recursion

Recursion

25 pages

Hashing

Hashing

24 pages

Recursion

Recursion

24 pages

Graphs

Graphs

25 pages

Storage

Storage

37 pages

Trees

Trees

21 pages

Arrays

Arrays

24 pages

Hashing

Hashing

24 pages

Recursion

Recursion

25 pages

Graphs

Graphs

23 pages

Graphs

Graphs

25 pages

Stacks

Stacks

25 pages

Recursion

Recursion

25 pages

Quicksort

Quicksort

21 pages

Quicksort

Quicksort

21 pages

Graphs

Graphs

25 pages

Recursion

Recursion

25 pages

Searching

Searching

24 pages

Counting

Counting

20 pages

HTML

HTML

18 pages

Recursion

Recursion

24 pages

Pruning

Pruning

11 pages

Graphs

Graphs

25 pages

Load more
Download Analysis of Algorithms
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Analysis of Algorithms and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Analysis of Algorithms 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?