Unformatted text preview:

Introduction to Algorithms6.046J/18.401JHow large should a hash table be?Example of a dynamic tableExample of a dynamic tableExample of a dynamic tableExample of a dynamic tableExample of a dynamic tableExample of a dynamic tableExample of a dynamic tableExample of a dynamic tableExample of a dynamic tableExample of a dynamic tableExample of a dynamic tableWorst-case analysisTighter analysisTighter analysisTighter analysis (continued)Amortized analysisTypes of amortized analysesAccounting methodAccounting analysis of dynamic tablesAccounting analysis of dynamic tablesAccounting analysis of dynamic tablesAccounting analysis (continued)Potential methodUnderstanding potentialsThe amortized costs bound the true costsThe amortized costs bound the true costsThe amortized costs bound the true costsPotential analysis of table doublingCalculation of amortized costsCalculation of amortized costsCalculation of amortized costsCalculationCalculationCalculationCalculationCalculationCalculationCalculationCalculationConclusionsOctober 31, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.1Introduction to Algorithms6.046J/18.401JLECTURE 13Amortized Analysis• Dynamic tables• Aggregate method• Accounting method• Potential methodProf. Charles E. LeisersonOctober 31, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.2How large should a hash table be?Goal: Make the table as small as possible, but large enough so that it won’t overflow (or otherwise become inefficient).Problem: What if we don’t know the proper size in advance?IDEA: Whenever the table overflows, “grow” it by allocating (via malloc or new) a new, larger table. Move all items from the old table into the new one, and free the storage for the old table.Solution: Dynamic tables.October 31, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.3Example of a dynamic table1. INSERT12. INSERToverflowOctober 31, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.4Example of a dynamic table1. INSERT112. INSERToverflowOctober 31, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.5Example of a dynamic table1. INSERT112. INSERT2October 31, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.6Example of a dynamic table1. INSERT112. INSERT223. INSERToverflowOctober 31, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.7Example of a dynamic table1. INSERT212. INSERT3. INSERToverflowOctober 31, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.8Example of a dynamic table1. INSERT12. INSERT23. INSERTOctober 31, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.9Example of a dynamic table1. INSERT2. INSERT3. INSERT4. INSERT4321October 31, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.10Example of a dynamic table1. INSERT12. INSERT233. INSERT4. INSERT5. INSERT4overflowOctober 31, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.11Example of a dynamic table1. INSERT2. INSERT43213. INSERT4. INSERT5. INSERToverflowOctober 31, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.12Example of a dynamic table1. INSERT2. INSERT1233. INSERT4. INSERT5. INSERT4October 31, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.13Example of a dynamic table1. INSERT2. INSERT3. INSERT4. INSERT6. INSERT65. INSERT5432177. INSERTOctober 31, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.14Worst-case analysisConsider a sequence of n insertions. The worst-case time to execute one insertion is Θ(n). Therefore, the worst-case time for ninsertions is n · Θ(n) = Θ(n2).WRONG! In fact, the worst-case cost for n insertions is only Θ(n) ≪ Θ(n2).Let’s see why.October 31, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.15Tighter analysisLet ci= the cost of the i th insertion=i if i –1is an exact power of 2,1 otherwise.i 12345678910sizei1 2 4 4 8 8 8 8 16 16ci1231511191October 31, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.16Tighter analysisLet ci= the cost of the i th insertion=i if i –1is an exact power of 2,1 otherwise.i 12345678910sizei1 2 4 4 8 8 8 8 16 16111111111112 4 8ciOctober 31, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.17Tighter analysis (continued)⎣⎦)(32 )1lg(01nnncnjjniiΘ=≤+≤=∑∑−==Cost of n insertions.Thus, the average cost of each dynamic-table operation is Θ(n)/n = Θ(1).October 31, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.18Amortized analysisAn amortized analysis is any strategy for analyzing a sequence of operations to show that the average cost per operation is small, even though a single operation within the sequence might be expensive.Even though we’re taking averages, however, probability is not involved!• An amortized analysis guarantees the average performance of each operation in the worst case.October 31, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.19Types of amortized analysesThree common amortization arguments:• theaggregate method,• theaccounting method,• thepotential method.We’ve just seen an aggregate analysis. The aggregate method, though simple, lacks the precision of the other two methods. In particular, the accounting and potential methods allow a specific amortized cost to be allocated to each operation.October 31, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.20Accounting method• Charge i th operation a fictitious amortized costĉi, where $1 pays for 1 unit of work (i.e., time).• This fee is consumed to perform the operation.• Any amount not immediately consumed is stored in the bank for use by subsequent operations.• The bank balance must not go negative! We must ensure that∑∑==≤niiniicc11ˆfor all n.• Thus, the total amortized costs provide an upper bound on the total true costs.October 31, 2005 Copyright © 2001-5 by Erik D. Demaine and Charles E. Leiserson L13.21Accounting analysis of dynamic tables$0$0$0$0$0$0$0$0$2$2$2$2Example:$2 $2Charge an amortized cost of ĉi=$3for the i th insertion.• $1 pays for the immediate insertion.• $2 is stored for later table doubling.When the table doubles, $1 pays to move a recent item, and $1 pays to move an old item.overflowOctober 31, 2005


View Full Document

MIT 6 046J - Amortized Analysis

Download Amortized Analysis
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 Amortized Analysis 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 Amortized Analysis 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?