复杂度震荡特殊情况

Question

bobo老师好！我想请问当capacity为2，size为1时，这个时候remove然后继续add算不算复杂度震荡呢，还是因为这种情况特殊且耗时忽略不计而不用考虑。

Answer 1

liuyubobobo 2019-07-24 02:57:29

赞问题和对边界条件的考虑！

我要没理解错，你想说的是，在这种情况下，remove会导致缩容，同时，再add又会扩容，产生不停的缩容扩容的情况。

虽然如此，但要明确，这种情况只有在capacity == 2 这样一个常数下情况发生。因此，缩容扩容的复杂度也是常数。这种震荡不会拓展到数据规模是 n 的情况。所以，我们的整个算法，平均复杂度依然是 O(1) 的，也就是常熟复杂度。

尽管如此，其实，一个更好地实现方案是，让我们的整个动态数组，容量值永远不要低于某一个阈值，比如10：）

继续加油！：）