通过非常数连续调整数组的大小
Resizing an array by a non-constant, continually
我想对动态数组进行摊销分析：
当我们执行 n 次插入序列时，每当大小为 k 的数组填满时，我们重新分配大小为 k+sqrt(k) 的数组，并将现有的 k 值复制到新数组中。
我是摊销分析的新手，这是我还没有遇到的问题，因为我们每次都会通过 不同的 非常量值调整数组的大小。 (newSize=prevSize+sqrt(prevSize))
总成本应为 Θ(n*sqrt(n))，因此每次操作为 Θ(sqrt(n))。
我意识到只要 k >= c^2 对于某个常量 c，我们的数组就会增长 c。
让我们从一个大小为 k=1 的数组开始（为了这个例子，假设 n 足够大）。在 n 次插入后，我们得到以下插入总成本 + 副本的总和：
1+1(=k)+1+2(=k)+1+3(=k)+1+4(=k)+2+6(=k)+2+8(= k)+2+10(=k)+3+13(=k)+3+16(=k)+4+20(=k)+4+24+4+28+5+33+5+38 +6+44+6+50+7…+n
我看到了模式，但我似乎无法计算边界。
我正在尝试使用各种摊销分析方法来绑定此汇总总和。
例如，让我们考虑会计方法，然后我认为每次插入我需要 round([k+sqrt(k)]\sqrt(k)) 或简单的 round(sqrt(k)+1) 硬币，但它不会添加向上。
我很想得到你的帮助，试图正确找到 sqrt(n) 的上限和下限。
非常感谢！ :)
最简单的方法是在下一次调整大小之前，将每个调整大小操作与紧随其后的插入集中在一起。
每个块的成本是O(k + sqrt(k))，每个块由O(sqrt(k))次操作组成，所以每次操作的成本是O( (k + k0.5)/k0.5) = O(k0.5 + 1) = O(k0.5)
当然你想要一个关于 if n 的答案，但是由于 k(n) 在 Θ(n) 中，O(k0.5) = O(N0.5).
这可以使用会计方法轻松显示。考虑一个大小为 k+sqrt(k) 的数组，其中前 k 个条目被占用，其余 sqrt(k) 为空。让我们制作Insert-Last个操作草案sqrt(k)+2个硬币：一个将用于支付插入，其余（sqrt(k)+1个硬币）将被存入并用于信用。从这里开始，执行 Insert-Last sqrt(k) 次。然后我们将有 k+sqrt(k) 个信用硬币：我们总共起草了 k+2sqrt(k) 个硬币，其中的 sqrt(k) 个用于支付插入费用。因此，我们不需要为数组的大小调整付费。一旦数组变满，我们就可以使用我们的 k+sqrt(k) 信用硬币并支付调整大小的操作。由于 k = Θ(n)，每个 Insert-Last 操作草稿 sqrt(k)+2 = O(sqrt(k)) = O(sqrt(n)) 个硬币，因此需要 O(sqrt(n)) 摊销.
我想对动态数组进行摊销分析： 当我们执行 n 次插入序列时，每当大小为 k 的数组填满时，我们重新分配大小为 k+sqrt(k) 的数组，并将现有的 k 值复制到新数组中。
我是摊销分析的新手，这是我还没有遇到的问题，因为我们每次都会通过 不同的 非常量值调整数组的大小。 (newSize=prevSize+sqrt(prevSize))
总成本应为 Θ(n*sqrt(n))，因此每次操作为 Θ(sqrt(n))。
我意识到只要 k >= c^2 对于某个常量 c，我们的数组就会增长 c。 让我们从一个大小为 k=1 的数组开始（为了这个例子，假设 n 足够大）。在 n 次插入后，我们得到以下插入总成本 + 副本的总和：
1+1(=k)+1+2(=k)+1+3(=k)+1+4(=k)+2+6(=k)+2+8(= k)+2+10(=k)+3+13(=k)+3+16(=k)+4+20(=k)+4+24+4+28+5+33+5+38 +6+44+6+50+7…+n
我看到了模式，但我似乎无法计算边界。 我正在尝试使用各种摊销分析方法来绑定此汇总总和。 例如，让我们考虑会计方法，然后我认为每次插入我需要 round([k+sqrt(k)]\sqrt(k)) 或简单的 round(sqrt(k)+1) 硬币，但它不会添加向上。
我很想得到你的帮助，试图正确找到 sqrt(n) 的上限和下限。
非常感谢！ :)
最简单的方法是在下一次调整大小之前，将每个调整大小操作与紧随其后的插入集中在一起。
每个块的成本是O(k + sqrt(k))，每个块由O(sqrt(k))次操作组成，所以每次操作的成本是O( (k + k0.5)/k0.5) = O(k0.5 + 1) = O(k0.5)
当然你想要一个关于 if n 的答案，但是由于 k(n) 在 Θ(n) 中，O(k0.5) = O(N0.5).
这可以使用会计方法轻松显示。考虑一个大小为 k+sqrt(k) 的数组，其中前 k 个条目被占用，其余 sqrt(k) 为空。让我们制作Insert-Last个操作草案sqrt(k)+2个硬币：一个将用于支付插入，其余（sqrt(k)+1个硬币）将被存入并用于信用。从这里开始，执行 Insert-Last sqrt(k) 次。然后我们将有 k+sqrt(k) 个信用硬币：我们总共起草了 k+2sqrt(k) 个硬币，其中的 sqrt(k) 个用于支付插入费用。因此，我们不需要为数组的大小调整付费。一旦数组变满，我们就可以使用我们的 k+sqrt(k) 信用硬币并支付调整大小的操作。由于 k = Θ(n)，每个 Insert-Last 操作草稿 sqrt(k)+2 = O(sqrt(k)) = O(sqrt(n)) 个硬币，因此需要 O(sqrt(n)) 摊销.