复杂度震荡特殊情况
来源：2-9 均摊复杂度和防止复杂度的震荡
慕粉4246227
2019-07-24
bobo老师好！我想请问当capacity为2，size为1时，这个时候remove然后继续add算不算复杂度震荡呢，还是因为这种情况特殊且耗时忽略不计而不用考虑。
写回答
1回答
-
liuyubobobo
2019-07-24
赞问题和对边界条件的考虑！
我要没理解错，你想说的是，在这种情况下，remove会导致缩容，同时，再add又会扩容，产生不停的缩容扩容的情况。
虽然如此，但要明确，这种情况只有在capacity == 2 这样一个常数下情况发生。因此，缩容扩容的复杂度也是常数。这种震荡不会拓展到数据规模是 n 的情况。所以，我们的整个算法，平均复杂度依然是 O(1) 的，也就是常熟复杂度。
尽管如此，其实，一个更好地实现方案是，让我们的整个动态数组，容量值永远不要低于某一个阈值，比如10：）
继续加油！：）
10
相似问题
关于复杂度震荡的防止
回答 1
哈希表 复杂度问题
回答 1