您能解释一下为什么正确答案是对数吗？我不明白。
假设，从一个空数据结构开始，我们在堆栈的调整大小数组实现中执行 n 个入栈操作。 resize() 方法被调用了多少次？
a) 常数
b) 对数(正确。仅当堆栈大小为 2 的幂时才调用 resize() 方法。1 和 n 之间有 ~log2n 2 的幂.)
c) 线性
d) 二次
最佳答案
为了容纳新元素，完全填充的动态数组(或您所说的调整大小数组)在推送新元素时其容量会增加一倍。对于动态数组的大多数常见实现来说都是如此。
最初，您的堆栈(通过动态数组实现)是空的。当您推送第一个元素时，它的大小会调整为 1 个元素的容量。当您按第二个时，它的大小会调整为 2 个元素的容量。当您按第三个时，它的大小会调整为 4 个元素的容量。因此，第四个元素的大小没有调整。但是，当您按第 5 个时，它的容量现在会调整为 8。如此往复。
因此，如果您要推送 n 个元素，则在推送第 1、2、3、5、9、17、...、元素时将调用 resize() .
那么resize()被调用了多少次？如果忽略第一个元素，则在推送第 (2^k + 1) 个元素时将调用 resize()，其中 k = 0,1， 2,3,4,5...。由于 [1,n] 范围内有近 log2(n) 个这样的数字，这就是 resize() 被调用的次数。因此，对数是正确的答案。
关于java - resize() 方法被调用了多少次？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/56957266/