Question? Leave a message!

Algorithm Analysis

Algorithm Analysis
Dr.SethPatton Profile Pic
Dr.SethPatton,United Kingdom,Teacher
Published Date:22-07-2017
Website URL
ECE 250 Algorithms and Data Structures Algorithm Douglas Wilhelm Harder, M.Math. LEL Analysis Department of Electrical and Computer Engineering University of Waterloo Waterloo, Ontario, Canada © 2006-2013 by Douglas Wilhelm Harder. Some rights reserved.Asymptotic Analysis 2 Outline In this topic, we will examine code to determine the run time of various operations We will introduce machine instructions We will calculate the run times of: – Operators +, -, =, +=, ++, etc. – Control statements if, for, while, do-while, switch – Functions – Recursive functionsAsymptotic Analysis 3 Motivation The goal of algorithm analysis is to take a block of code and determine the asymptotic run time or asymptotic memory requirements based on various parameters – Given an array of size n: 2 • Selection sort requires Q(n ) time • Merge sort, quick sort, and heap sort all require Q(n ln(n)) time – However: • Merge sort requires Q(n) additional memory • Quick sort requires Q(ln(n)) additional memory • Heap sort requires Q(1) memory Asymptotic Analysis 4 Motivation The asymptotic behaviour of algorithms indicates the ability to scale – Suppose we are sorting an array of size n 2 Selection sort has a run time of Q(n ) 2 2 – 2n entries requires (2n) = 4n • Four times as long to sort 2 2 – 10n entries requires (10n) = 100n • One hundred times as long to sortAsymptotic Analysis 5 Motivation The other sorting algorithms have Q(n ln(n)) run times – 2n entries require (2n) ln(2n) = (2n) (ln(n) + 1) = 2(n ln(n)) + 2n – 10n entries require (10n) ln(10n) = (10n) (ln(n) + 1) = 10(n ln(n)) + 10n In each case, it requires Q(n) more time However: – Merge sort will require twice and 10 times as much memory – Quick sort will require one or four additional memory locations – Heap sort will not require any additional memoryAsymptotic Analysis 6 Motivation lg(3) We will see algorithms which run in Q(n ) time – lg(3) ≈ 1.585 lg(3) lg(3) lg(3) lg(3) – For 2n entries require (2n) = 2 n = 3 n • Three times as long to sort lg(3) lg(3) lg(3) lg(3) – 10n entries require (10n) = 10 n = 38.5 n • 38 times as long to sort Asymptotic Analysis 7 Motivation lg(3) We will see algorithms which run in Q(n ) time – lg(3) ≈ 1.585 lg(3) lg(3) lg(3) lg(3) – For 2n entries require (2n) = 2 n = 3 n • Three times as long to sort lg(3) lg(3) lg(3) lg(3) – 10n entries require (10n) = 10 n = 38.5 n • 38 times as long to sort Binary search runs in Q(ln(n)) time: – Doubling the size requires one additional searchAsymptotic Analysis 8 Motivation If we are storing objects which are not related, the hash table has, in many cases, optimal characteristics: – Many operations are Q(1) – I.e., the run times are independent of the number of objects being stored If we are required to store both objects and relations, both memory and time will increase – Our goal will be to minimize this increaseAsymptotic Analysis 9 Motivation To properly investigate the determination of run times asymptotically: – We will begin with machine instructions – Discuss operations – Control statements • Conditional statements and loops – Functions – Recursive functionsAsymptotic Analysis 10 Machine Instructions Given any processor, it is capable of performing only a limited number of operations These operations are called instructions The collection of instructions is called the instruction set – The exact set of instructions differs between processors – MIPS, ARM, x86, 6800, 68k – You will see another in the ColdFire in ECE 222 • Derived from the 68000, derived from the 6800Asymptotic Analysis 11 Machine Instructions Any instruction runs in a fixed amount of time (an integral number of CPU cycles) An example on the Coldfire is: 0x06870000000F th which adds 15 to the 7 data register As humans are not good at hex, this can be programmed in assembly language as ADDI.L F, D7 – More in ECE 222Asymptotic Analysis 12 Machine Instructions Assembly language has an almost one-to-one translation to machine instructions – Assembly language is a low-level programming language Other programming languages are higher-level: Fortran, Pascal, Matlab, Java, C++, and C The adjective ―high‖ refers to the level of abstraction: – Java, C++, and C have abstractions such as OO – Matlab and Fortran have operations which do not map to relatively small number of machine instructions: 1.272.9 % 1.272.9 in Fortran 2.0000036616123606774Asymptotic Analysis 13 Machine Instructions The C programming language (C++ without objects and other abstractions) can be referred to as a mid-level programming language – There is abstraction, but the language is closely tied to the standard capabilities – There is a closer relationship between operators and machine instructions Consider the operation a += b; – Assume that the compiler has already has the value of the variable a in register D1 and perhaps b is a variable stored at the location stored in address register A1, this is then converted to the single instruction ADD (A1), D1Asymptotic Analysis 14 Operators Because each machine instruction can be executed in a fixed number of cycles, we may assume each operation requires a fixed number of cycles – The time required for any operator is Q(1) including: • Retrieving/storing variables from memory • Variable assignment = • Integer operations + - / % ++ • Logical operations && • Bitwise operations & • Relational operations == = = = • Memory allocation and deallocation new deleteAsymptotic Analysis 15 Operators Of these, memory allocation and deallocation are the slowest by a significant factor – A quick test on eceunix shows a factor of over 100 – They require communication with the operation system – This does not account for the time required to call the constructor and destructor Note that after memory is allocated, the constructor is run – The constructor may not run in Q(1) timeAsymptotic Analysis 16 Blocks of Operations Each operation runs in Q(1) time and therefore any fixed number of operations also run in Q(1) time, for example: // Swap variables a and b int tmp = a; a = b; b = tmp; // Update a sequence of values // ++index; prev_modulus = modulus; modulus = next_modulus; next_modulus = modulus_tableindex;Asymptotic Analysis 17 Blocks of Operations Seldom will you find large blocks of operations without any additional control statements This example rearranges an AVL tree structure Tree_node lrl = left-right-left; Tree_node lrr = left-right-right; parent = left-right; parent-left = left; parent-right = this; left-right = lrl; left = lrr; Run time: Q(1)Asymptotic Analysis 18 Blocks in Sequence Suppose you have now analyzed a number of blocks of code run in sequence template typename T void update_capacity( int delta ) Q(1) T array_old = array; int capacity_old = array_capacity; array_capacity += delta; array = new Tarray_capacity; for ( int i = 0; i capacity_old; ++i ) Q(n) arrayi = array_oldi; delete array_old;Q(1) or W(n) To calculate the total run time, add the entries: Q(1 + n + 1) = Q(n)Asymptotic Analysis 19 Blocks in Sequence This is taken from code found at template int M, int N MatrixM, N &MatrixM, N::operator= ( MatrixM, N const &A ) if ( &A == this ) return this; Q(1) if ( capacity = A.capacity ) delete column_index; delete off_diagonal; capacity = A.capacity; Q(1 + 1 + min(M, N) + M + n + 1) Q(1) column_index = new intcapacity; off_diagonal = new doublecapacity; = Q(M + n) for ( int i = 0; i minMN; ++i ) diagonali = A.diagonali; Q(min(M, N)) for ( int i = 0; i = M; ++i ) row_indexi = A.row_indexi; Note that min(M, N) ≤ M but we Q(M) cannot say anything about M and n for ( int i = 0; i A.size(); ++i ) column_indexi = A.column_indexi; off_diagonali = A.off_diagonali; Q(n) return this; Q(1) Asymptotic Analysis 20 Blocks in Sequence Other examples include: 2 – Run three blocks of code which are Q(1), Q(n ), andQ(n) 2 2 Total run time Q(1 + n + n) = Q(n ) 1.5 – Run two blocks of code which are Q(n ln(n)), andQ(n ) 1.5 1.5 Total run time Q(n ln(n) + n ) = Q(n ) Recall this linear ordering from the previous topic – When considering a sum, take the dominant term