[名词解释]Constant Amortized Time
http://stackoverflow.com/questions/200384/constant-amortized-time
分摊常量时间:
Amortised time explained in simple terms:
If you do an operation say a million times, you don't really care about the worst-case or the best-case of that operation - what you care about is how much time is taken in total when you repeat the operation a million times.
So it doesn't matter if the operation is very slow once in a while, as long as "once in a while" is rare enough for the slowness to be diluted away. Essentially amortised time means "average time taken per operation, if you do many operations". Amortised time doesn't have to be constant; you can have linear and logarithmic amortised time or whatever else.
Let's take mats' example of a dynamic array, to which you repeatedly add new items. Normally adding an item takes constant time (that is, O(1)
). But each time the array is full, you allocate twice as much space, copy your data into the new region, and free the old space. Assuming allocates and frees run in constant time, this enlargement process takes O(n)
time where n is the current size of the array.
So each time you enlarge, you take about twice as much time as the last enlarge. But you've also waited twice as long before doing it! The cost of each enlargement can thus be "spread out" among the insertions. This means that in the long term, the total time taken for adding m items to the array is O(m)
, and so the amortised time (i.e. time per insertion) is O(1)
.
最新文章
- html5 历史管理onhashchange和state
- 关于jQuery外部框架
- ADB 常用命令总结(持续更新)
- 【LeetCode OJ】Valid Palindrome
- Codeforces Round #306 (Div. 2) D. Regular Bridge 构造
- 通过redis-rdb-tools分析redis内存使用量
- 基于visual Studio2013解决C语言竞赛题之1036递归求值
- 一次失败的刷题经历:[LeetCode]292之尼姆游戏(Nim Game)(转)
- python数据挖掘_Json结构分析
- bzoj 4008: [HNOI2015]亚瑟王
- ACM Wooden Stricks
- supervisor支持python虚拟环境venv
- j假设程序需要要一个int烈血的刀变量来保存1英里所包含的步数(5280)为该变量编写一条声明语句。
- HTML自动跳转
- 简单理解Linux的Loopback接口
- Django项目----快速实现增删改查组件(起步阶段!!!)
- 异步编程之asyncio简单介绍
- spring+spring mvc+JdbcTemplate 入门小例子
- learngin uboot design parameter recovery mechanism
- mysql5.5以上开启慢查询