Complexity in Programming Fundamentals: Understanding Performance Analysis
In this lecture, we delve into the analysis of program performance, emphasizing correctness, maintainability, modularity, and simplicity. Premature optimization pitfalls are discussed, along with examples of estimating performance using concepts like Big-O notation.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
ECE 244 Programming Fundamentals Lec.26: Complexity 1 Ding Yuan ECE Dept., University of Toronto http://www.eecg.toronto.edu/~yuan
Overview We are going to discuss analysis of program s performance But remember, performance is less important than: Correctness Maintainability Modularity (e.g., good class hierarchy) + simplicity Functionality Extensibility Reliability Security User friendliness Scalability
Premature optimization is the root of all devils Most programmers predict poorly which areas are performance bottleneck They tend to optimize code too early and unnecessarily Lead to complex & buggy programs Premature optimization! It s better to write simple, correct program and then analyze its performance later Detect & optimize bottleneck
Expressed in terms of input size Input size n Linear search of linked list on fast computer 7 ns 32 ns 128 ns 500 ns 500,000 ns 8,000,000 ns 3 * 10^16 ns = 1 year Binary search tree on slow computer 100,000 ns 150,000 ns 200,000 ns 250,000 ns 500,000 ns 600,000 ns 1,375,000 ns = 1.375 sec 15 65 250 1,000 1,000,000 16,000,000 6 * 10^16 Cost of individual instructions don t matter Differences of a factor 2 or 3 (or 4 or 5 ) don t matter Just get a faster computer
Examples of estimating perf. a = b; T(n) = 1 for (int i = 0; i < n; i++) why 3? addition, increment, sum += i; comparison sum = 0; T(n) = 2 + 3*n for (i = 0; i < n; i++) Best case: T(n) = 4 if (a[i] == value) Worst case: T(n) = 1 + 3*n return i; Average case: T(n) = 1 + C*n Linear search In all these cases, T(n) is an approximation Actual running time depends on Computer speed Language Compiler
Big-O notation (where O is the letter Oh) When comparing algorithms, we are not interested in constants (b/c a faster computer can make up any difference) We are only interested in the highest order term (b/c that dominates) We say T(n) is on the order of O(f(n)) if T(n) s highest order term is f(n), disregarding constants Formally: T(n) is in O(f(n)) if constant C, N, so that T(n) C f(n) for every n > N
Examples a = b; T(n) = 1 -> O(1) O(n) for (int i = 0; i < n; i++) why 3? addition, increment, sum += i; comparison sum = 0; T(n) = 2 + 3*n for (i = 0; i < n; i++) Best case: T(n) = 4 if (a[i] == value) Worst case: T(n) = 1 + 3*n return i; Average case: T(n) = 1 + C*n Linear search O(1) O(n)
More Examples: Matrix Multiply double a[N][N]; double b[N][N]; double c[N][N];// initialized to 0 /* Multiply N x N matrices a and b */ int i, j, k; for (i = 0; i < N; i++) for (j = 0; j < N; j++) for (k = 0; k < N; k++) c[i][j] += a[i][k] * b[k][j]; A B 1 2 3 4 1 2 3 4 5 6 7 8 5 6 7 8 9 10 11 12 9 10 11 12 13 14 15 16 13 14 15 16 T(n) C1 n3 + C2 O(n3)
Facebook Homepage foreach (friend in friendList) // assume n friends foreach (update of friend) // assume m recent updates display update; O(n m) If m is a constant, i.e., 3, then it s O(n)
Insertion sort for (i = 0; i <n; i++) for (j = i; j > 0 && a[j] < a[j-1]; j--) swap(a[j], a[j-1]); Best case: T(n) C n = O(n) Worst case: T(n) C(n + (n-1) + (n-2) + .. +1) = C*n(n+1)/2 = O(n2) Avg. case: for each iteration in the outer loop, needs to swap w/ half of the elements in a[0]-a[i] C*( * n + * (n-1) + + * 2 + 1) = C * n(n+1)/4 = O(n2) 2 4 7 8 5 3 9 ^ ^____| | |________|
Binary search on sorted array bool search (int first, int last, int key, int & index) { if (first > last) return false; int mid = (first + last) /2 ; if (key == a[mid]) { index = mid; return true; } if (key < a[mid]) return search (first, mid-1, key, index); else return search(mid+1, last, key, index); } search for 2 in: [0 1 [[2] 3]] 4 5 6 7 8 T(n) = C + T(n/2) = C + (C + T(n/4)).. Problem size: n n/2 n/4 .. 1 O(log(N))
Why focus on big-O analysis? We saw example where we compared O(n) algorithm on fast computer vs. O(log(n)) algorithm on slow computer On larger n, O(log(n)) algorithm is much faster than O(n) algorithm even on much slower computer Focus on big-O analysis n 2 16 256 1024 log(n) 1us 4us 8us 10us n*log(n) 2us 64us 2ms 10ms n2 4us 256us 65ms 1s n3 8us 4ms 16s 17min. 2n (exponential) 4us 65ms 4*1063 years 6*10294 years Assume 1 operation takes 1us (microsecond)
