Constant Amortized time恒定分摊时间

在上一节讨论CPU的流水线工作机制的时候,提到了一个算法复杂度的衡量原则,即Amortized Time,这次我们要讨论的是Constant Amortized Time,先在StackOverflow上面搜索了一下,有相关的内容,但是赞成人数不是特别多,我先翻译一下简单版本的解释,如果大家想看更详细的介绍,请移步到这里来what’s amortized time

当我们讨论算法复杂度的时候,恒定分摊时间是什么意思呢?

举个例子简单解释一下:

如果一个操作执行100万次,那么就不会关心其中最快的一次或者最慢的一次耗费了多长时间,而是执行100万次操作总共耗费了多长时间。

所以执行一次很慢确实不太重要,只是偶尔一次很慢在大批量执行的情况下会被摊销,所以恒定分摊时间就意味着是执行一次操作的平均时间,如果执行的次数够多,分摊时间不一定就是常量,也有可能是线性或者对数分摊时间。

我们来看一个动态数组新增元素的例子(java中可以参考ArrayList),通常新增一个元素所耗费的时间就是常量O(1),但是每一次当数组被填充满了,需要扩容到原来的2倍,然后会生成一个新数组,并且把老数组里面的元素复制到新数据当中去,释放老数据内存空间,假设分配新数组空间和释放老数组内存空间耗费时间都是常量,新增一个元素的时间会放大到O(n),n就是当前数组的大小。

所以每一次数组的扩容,都会花费最后一次扩容2倍的时间,在扩容之前也等待了2次同样的时间,因此每次扩容的时间可以分摊到每次新增元素的时间中,这意味着如果数据够大,从长远来看,将m个元素添加到动态数组中花费的时间是O(m),因此单个新增耗费的时间就是O(1)。

翻译完。

转载请标示: http://hushengdomg.com/2016/12/19/Constant-Amortized-time恒定分摊时间/

java是值传递还是引用传递

java中到底是值传递还是引用传递呢?自开始编程就一直在讨论这个问题,从stackoverflow中查看热门问题,排名第3,所以决定翻译一下 原文链接,我个人比较倾向于第2位投票数的答案,所以翻译的也是他的答案,并给出了这位作者的网址。问题很简单,也没有什么背景需要介绍,就不翻译了。

点击阅读全文