Amortization: Difference between revisions
Jump to navigation
Jump to search
(Created page with "<!-- -->") |
mNo edit summary |
||
| (One intermediate revision by the same user not shown) | |||
| Line 1: | Line 1: | ||
{{stub}} | |||
<!-- | <!-- | ||
Amortization has a few different meanings within finance, and one in computing. | |||
They all relate to cost over time in some way. | |||
In accounting, amortization refers to occasionaly lowering the book value of a loan (or such) | |||
because you are writing off a cost over a period.{{verify}} | |||
[[Computational_complexity_theory_notes#Worst,_average_and_best_case;_amortized_analysis|In computational complexity theory, amortization]] | |||
roughly means "based on an analysis of howmany operations it will ''really'' need, rather than back-of-napkin extrapolation. | |||
Amortized analysis would say "well let's take the average over a lot of work". | |||
When it would give a different answer to worst-case analysis or average-case analysis, it is usually interesting to know why. | |||
...which exists in part because things like "Oh it's probably O(n<sup>2</sup>)" can easily be too ''pessimistic'' because it's worst-casing. | |||
Consider a dynamic array: an array within an allocated block, and whenever it's full you allocate an array twice its size and copy things there. | |||
Worst case analysis would point out that if you want hard guarantees, then you should assume the worst case. Which is O(n). | |||
Yet the larger it grows, the more that ''most'' insertions will actually be O(1). | |||
You might want the generic answer to be O(n) because . | |||
In fact that doubling-the-size almost even partially offsets the "we don't care about the details, we only care know the way it grows so we can select the one that scales best" | |||
But in an everyday sense, this is an example where this implementation might be fundamentally and noticeably faster than | |||
a really dumb dynamic array implementation (such as reallocating each insert). | |||
--> | --> | ||
Latest revision as of 13:15, 28 April 2024
✎ This article/section is a stub — some half-sorted notes, not necessarily checked, not necessarily correct. Feel free to ignore, or tell me about it.