Kĩ thuật lập trình - Big - O analysis of algorithms

Big-O Analysis of AlgorithmsCopyright © 2011 by Maria Litvin, Gary Litvin, and Skylight Publishing. All rights reserved.Java MethodsObject-Oriented Programmingand Data StructuresMaria Litvin ● Gary Litvin2nd AP edition  with GridWorld1Objectives:Learn the big-O definition and notationReview big-O for some common tasks and algorithms studied earlierReview several popular sorting algorithms and their average, best, and worst case big-O2Evaluation of AlgorithmsPractice:benchmarksTheory:asymptotic analysis, big-Otn3Analysis of Algorithms — AssumptionsAbstract computer model with “unlimited” RAMUnlimited range for integersBasic operations on integers (addition, multiplication, etc.) take fixed time regardless of the values of the operands4Big-O AnalysisStudies space and time requirements in terms of the “size” of the taskThe concept of “size” is somewhat informal here:The size of a list or another collectionThe dimensions of a 2-D arrayThe argument of a function (for example, factorial(n) or fibonacci(n))The number of objects involved (for example, n disks in the Tower of Hanoi puzzle)5Big-O AssumptionsHere our main concern is timeIgnores a constant factormeasures the time in terms of the number of some abstract stepsApplies to large n, studies asymptotic behavior6Example 1: Sequential Searchfor (int i = 0; i N.11Big-O (cont’d)Big-O means that asymptotically t(n) grows not faster than g(n).In analysis of algorithms, it is common practice to use big-O for the tightest possible upper bound.Example:Sequential Search is O(n)Binary Search is O(log n)like “t(n)  g(n)” like “t(n) = g(n)” 12Big-O (cont’d)For a log, the base is not important: from the Change of Base Theorem where13Big-O (cont’d)For a polynomialthe big-O is determined by the degree of the polynomial:14Big-O (cont’d)For “triangular” nested loops The total number of iterations is:for (int i = 0; i 1) — exponential timeRecursive Fibonacci implementation (a  3/2; see Chapter 23)Solving the Tower of Hanoi puzzle (a = 2; see Section 23.5)Generating all possible permutations of n symbols21Big-O SummaryO(1)   1) { iMax = 0; for (int i = 1; i a [ iMax ]) iMax = i; swap (a, iMax, n-1); n--; }Always n(n-1)/2 comparisons25Insertion Sort — O(n2)Keep the beginning of the list sorted.Insert the next value in order into the sorted. beginning segment. for (int i = 1; i 0 && a [ j-1 ] > temp; j--) a [ j ] = a [ j-1 ]; a [ j ] = temp; }O(n2) comparisons on average, but only O(n) when the list is already sorted26Mergesort — O(n log n)Split the list down the middle into two lists of approximately equal length.Sort (recursively) each half.Merge the two sorted halves into one sorted list. private void sort (double a [ ], int from, int to) { if (to == from) return; int middle = (from + to) / 2; sort(a, from, middle); sort(a, middle + 1, to); merge (a, from, middle, middle + 1, to); }Each merge takes O(n) comparisons27Quicksort — O(n log n)Choose a “pivot” element.Partition the array so that all the values to the left of the pivot are smaller than or equal to it, and all the elements to the right of the pivot are greater than or equal to it.Sort (recursively) the left-of-the-pivot and right-of-the-pivot pieces.Proceed from both ends of the array as far as possible; when both values are on the wrong side of the pivot, swap themO(n log n) comparisons, on average, if partitioning splits the array evenly most of the time28Heapsort — O(n log n)An elegant algorithm based on heaps (Chapter 26)29Sorting Summary30Review:What assumptions are made for big-O analysis?What O(...) expressions are commonly used to measure the big-O performance of algorithms?Is it true that n(n-1)/2 = O(n2)?Give an example of an algorithm that runs in O(log n) time.Give an example of an algorithm (apart from sorting) that runs in O(n2) time.31Review (cont’d):Name three O(n log n) sorting algorithms.How many comparisons are needed in sorting by counting? In Selection Sort?What is the main idea of Insertion Sort?What is the best case for Insertion Sort?What is the main idea of Quicksort?What is the worst case for Quicksort?32