Algorithm Analysis and Types: Understanding Running Time and Efficiency
Algorithm analysis involves evaluating the performance and efficiency of algorithms based on different scenarios like worst-case, average-case, and amortized analysis. This analysis helps in understanding the running time of algorithms and making informed decisions about their implementation. Quicksort, a widely-used sorting algorithm, serves as an example to illustrate these concepts. The process involves partitioning elements and recursively sorting them to achieve optimal time complexity. By analyzing quicksort in both worst and best-case scenarios, one can gain insights into the differences in time complexity and efficiency. Overall, algorithm analysis is crucial for optimizing algorithms and improving computational processes.
Uploaded on Feb 24, 2025 | 0 Views
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
Types of Analysis 1. Worst-case analysis Analyze running time as function of worst input of a given size. 2. Average case analysis Analyze average running time over some distribution of inputs. 3. Amortized analysis Worst-case bound on a sequence of operations. 4. Competitive analysis Make quantitative statements about online algorithms. 2
Average Case Analysis Analyze average running time over some distribution of inputs. Example: quicksort. O(n log n) if input is assumed to be in random order. leads to randomized algorithm with O(n log n) expected running time, independent of input 3
Quicksort qsort(int first, int last) { int mid; if (last>first) { mid = partition(first, last); qsort(first. mid-1); qsort(mid+1, last); } } <pivot pv >pivot <pv >pv <pv >pv 4
The Partition Algorithm int partition(int first, int last) { pivot = a[first]; p1 = first+1; p2 = last; while (p1<=p2) { while( a[p1] <= pivot) ++p1; while( a[p2] >= pivot) --p2; if (p1<p2) swap(a[p1], a[p2]); else swap(a[first], a[p2]); } return p2; } 5
Partition: Example p1 p2 sentinel pivot 24 8 48 20 15 43 12 7 50 35 31 24 8 7 20 15 43 12 48 50 35 31 24 8 7 20 15 12 43 48 50 35 31 12 8 7 20 15 24 43 48 50 35 31 6 6
Quick Sort: Example p2 p1 pivot 24 8 48 20 15 43 12 7 50 35 31 12 8 7 20 15 24 43 48 50 35 31 43 48 50 35 31 12 8 7 20 15 7 8 12 20 15 35 31 43 50 48 7 8 7 8 20 15 15 20 35 31 31 35 50 48 48 50 7 7
Analyzing Quicksort In the worst case: T(1) = c T(n) = T(n - 1) + nc Works out to T(n) = O(n2) In the best case: T(n) = 2T(n/2) + nc Works out to T(n) = O(n lg n) 8 8
Average case analysis qsort(int first, int last) { int mid; if (last>first) { mid = partition(first, last); qsort(first. mid-1); qsort(mid+1, last); } } nc T(mid-1) T(n-mid) T(n) = T(mid-1) + T(n-mid) + nc 9
Average case analysis conti1 To simply math, T(n) = T(mid-1) + T(n-mid) + (n+1)c mid 1 T(n) = T( 0 ) + T(n-1) + (n+1)c 2 T(n) = T( 1 ) + T(n-2) + (n+1)c . . . n-1 T(n) = T(n-2) + T( 1 ) + (n+1)c n T(n) = T(n-1) + T( 0 ) + (n+1)c
Average case analysis conti2 Assume that all numbers are equally likely. mid 1 1/n * ( T( 0 ) + T(n-1) + (n+1)c ) 2 1/n * ( T( 1 ) + T(n-2) + (n+1)c ) .. . . . n-1 1/n * ( T(n-2) + T( 1 ) + (n+1)c ) n + 1/n * ( T(n-1) + T( 0 ) + (n+1)c ) . T(n) = 2/n * ( T(0) + T(1) + + T(n-1) ) + (n+1)c nT(n) = 2 ( T(0) + T(1) + + T(n-1) ) + n(n+1)c (1) Replacing n by n-1 in (1) (n-1)T(n-1) = 2 ( T(0) + T(1) + + T(n-2) ) + (n-1)nc (2)
Average case analysis conti3 Subtracting (2) from (1) we get nT(n)-(n-1)T(n-1) = 2T(n-1) + 2nc Combine 2 T(n-1) terms, nT(n) = (n+1)T(n-1) + 2nc (3) Divide (3) by n(n+1) T(n)/(n+1) = T(n-1)/n + 2c/(n+1) Do iterative expansion we get T(n)/(n+1) = T(n-2)/(n-1) + 2c/n + 2c/(n+1) = T(n-3)/(n-2) + 2c/(n-1) + 2c/n + 2c/(n+1) . . . = 2c 1/k 2c 3 k n+1 n+2 1 dx x 2
Average case analysis conti4 T(n)/(n+1) 2c(log (n+2) log 2) Thus, T(n) 2(n+1)c log (n+2) = O(n log n).
Amortized Analysis Worst-case bound on a sequence of operations. no probability involved Example: union-find. sequence of m union and n find operations starting with n singleton sets takes O((m+n) (n)) time. single find operation might be expensive, but only (n) on average. 14
Formal Schemes for Amortized Analysis 1. Aggregate method. 2. Accounting method. 3. Potential method. 15
The Aggregate Method Evaluate the overall worst-case cost T(n) (an upper bound) on the total cost of a sequence of n operations. In the worst case, the average cost, or amortized cost, per operation is therefore T(n)/n. Note that the amortized cost for any operation is the same in the aggregate method. On the contrary, the accounting method and the potential method, may assign different amortized costs to different types of operations. 16
Example: Two-Stack System Suppose there are two stacks called A and B, manipulated by the following operations: push(S, e): Push element e onto stack S. Real Cost = 1. multi-pop(S, k): Removes min(k, |S|) elements from stack S. Real Cost = min(k, |S|). transfer(k): Repeatedly pop elements from stack A and push them onto stack B. until either k elements have been moved, or A is empty. Real Cost = # of elements moved = min(k, |A|). 17
A simple worst case analysis Start with an empty stack and n elements A stack can be as large as O(n). So a multipop operation could have a complexity of O(n). Since there are n operations, an upper bound of the total complexity is O(n2). Although this is a valid upper bound, it grossly overestimates the upper bound. 18
Illustration Given a sequence of n operations n push operations n elements popped n elements transferred A B 19
Aggregate Method For a sequence of n operations, there are n data pushed into either A or B. Therefore there are n data popped out from either A or B and n data transferred from A to B. Thus, the total cost of the n operations is 3n. Thus. Operation Push(A, d) Push(B, d) Multipop(A, k) min(k, |A|) Multipop(B, k) min(k, |B|) Transfer(k) Real Cost 1 1 Amortized Cost 3 3 3 3 3 min(k, |A|) 20
The Accounting Method Assign fixed (possibly different) costs to operations. Compute the aggregate cost based on the fixed costs. There are operations that are overpaid as well as those that are underpaid. The accounting method overcharges some operations early in the sequence, storing the overcharge as "prepaid credit" on specific objects in the data structure. The credit is used later in the sequence to pay for operations that are charged less than they actually cost. Argue that the total underpayment does not exceed the total overpayment. 21
Illustration Push(A,d) Pop(A,d) Pop(B,d) Transferred() B A 22
Accounting Method push(A, d): $3 -- This pays for the push and a pop of the push a transfer and a pop. push(B, d): $2 -- This pays for the push and a pop. multi-pop(S, k): $0 transfer(k): $0 After any n operations you will have |A| + |B| dollars in the bank. Thus the bank account never goes negative. Furthermore the amortized cost of the n operations is O(n) (more precisely 3n). 23
Comparison Operation Real Cost Aggre- Accoun- ting 3 Potential gate 3 Push(A, d) 1 Push(B, d) 1 3 2 Multipop(A, k) min(k, |A|) 3 0 Multipop(B, k) min(k, |B|) 3 0 Transfer(k) min(k, |A|) 3 0 24
Online Algorithms Definition: An algorithm that must process each input in turn, without detailed knowledge of future inputs. Examples: Ski Rental, List Update 25
Example Online Problem: Ski Rental Problem Scenario I am a skier. Each day, I have to either rent a pair of skis for $1 per day, or buy them for $T. BUT I don t know when the ski season will end. First Strategy: I will buy the skis on the first day. Second Strategy: I will keep renting the skis. Third Strategy:I ll rent the skis for T days, and buy them on the T+1st day. 26
Competitive Analysis Definition: An analysis in which the performance of an online algorithm is compared to the best that could have been achieved if all the inputs had been known in advance. Algorithm A is k-competitive if there exists some constant b such that for every sequence of inputs S : COSTA(S) k COSTOPT(S) + b where OPT is optimal offline algorithm. Claim: The third strategy is 2-competitive. 27
List Update Problem Self-organizing sequential search Unsorted list y w z x v u L: Received a sequence of requests r1, r2, r3, .. Cost of accessing the ith element of the list is i. 28
Move-to-Front (MTF) When an element is accessed, move it to the front of the list. Theorem: [Sleator, Tarjan, 1985] MTF has competitive ratio 2 against optimal offline algorithm. 29
FREQUENCY-COUNT (FC) Maintain a frequency counter for each item, and keep the list in nonincreasing order of their frequencies. FC has a bad competitive ratio = (n), where n is the length of the list. 30
