Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.0k views
in Technique[技术] by (71.8m points)

algorithm - Amortized time of dynamic array

As a simple example, in a specific implementation of the dynamic array, we double the size of the array each time it fills up. Because of this, array reallocation may be required, and in the worst case an insertion may require O(n). However, a sequence of n insertions can always be done in O(n) time, because the rest of the insertions are done in constant time, so n insertions can be completed in O(n) time. The amortized time per operation is therefore O(n) / n = O(1). --from Wiki

But in another book :Each doubling takes O(n) time, but happens so rarely that its amortized time is still O(1).

Hope somebody could tell me does the rare situation infer the Wiki explanation? Thanks

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Answer

0 votes
by (71.8m points)

Amortized basically means average per number of operations.

So, if you have an array of n, you need to insert n+1 items until you'll need the reallocation.

So, you've done n inserts which each one of them took O(1), and another insert that took O(n), so in total you've got n+1 actions that cost you 2n operations .

2n / n+1  ~= 1 

That's why the Amortized time is still O(1)


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...