04 | 复杂度分析（下）：浅析最好、最坏、平均、均摊时间复杂度

作者：鲁米

2023-12-03
北京
本文字数：663 字
阅读完需：约 2 分钟

我们今天学的几个复杂度分析方法，你都掌握了吗？你可以用今天学习的知识，来分析一下下面这个 add() 函数的时间复杂度。

// 全局变量，大小为10的数组array，长度len，下标i。int array[] = new int[10]; int len = 10;int i = 0;
// 往数组中添加一个元素void add(int element) {   if (i >= len) { // 数组空间不够了     // 重新申请一个2倍大小的数组空间     int new_array[] = new int[len*2];     // 把原来array数组中的数据依次copy到new_array     for (int j = 0; j < len; ++j) {       new_array[j] = array[j];     }     // new_array复制给array，array现在大小就是2倍len了     array = new_array;     len = 2 * len;   }   // 将element放到下标为i的位置，下标i加一   array[i] = element;   ++i;}

复制代码

1. `add` 方法中的数组扩容部分：

在每次插入操作之前，首先检查是否需要扩容。如果需要，就申请一个新的数组，然后将原来数组的元素复制到新数组。
复制元素的操作需要遍历原数组，所以这一部分的时间复杂度为 O(len)，其中 len 表示数组的当前长度。
由于每次扩容都是在数组满时进行，平均每次插入操作需要进行数组扩容，但由于扩容的次数是递增的，可以看作是一个摊还复杂度，均摊复杂度为 O(1)。

2. `add` 方法中元素插入部分：

元素的插入操作是在数组中的下一个位置进行的，即 O(1) 操作。

整体时间复杂度：

对于 n 次插入操作，add 方法的均摊时间复杂度为 O(1)。这是因为虽然扩容的操作会导致某些插入操作花费较多时间，但这些操作是渐进递增的，平摊到每次插入，时间复杂度是常数级别的。

发布于: 刚刚阅读数: 2

原文链接:【http://xie.infoq.cn/article/7837137a8dc06d7b104465d24】。

鲁米

关注

生活黑客35 2019-06-11 加入

起点不重要，迭代很重要，就需要保持充分的开放和积累；而信息越充分，结果越可靠，又要求随时调整、不断逼近真相。

发布

暂无评论

创作场景

04 | 复杂度分析（下）：浅析最好、最坏、平均、均摊时间复杂度

1. add 方法中的数组扩容部分：

2. add 方法中元素插入部分：

整体时间复杂度：

鲁米

评论

1. `add` 方法中的数组扩容部分：

2. `add` 方法中元素插入部分：