如果现在将索引k的位翻转为2 ^ k而不是1，那么二进制计数器中的摊销分析会怎样？

本文介绍了如果现在将索引k的位翻转为2 ^ k而不是1，那么二进制计数器中的摊销分析会怎样？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述 29岁程序员，3月因学历无情被辞！ 假设翻转位＃ i 花费2 ；因此，翻转比特0的成本为1，翻转比特1的成本为2，翻转比特2的成本为4，依此类推。Suppose that flipping bit #i costs 2; so, flipping bit #0 costs 1, flipping bit #1 costs 2, flipping bit #2 costs 4, and so on.通话的摊销成本是多少到 Increment（），如果我们称之为 n 次？What is the amortized cost of a call to Increment(), if we call it n times?我认为 n 的增量成本应为 n ·2 / 2 ++ nbsp; n ·2 / 2   +  n ·2 / 2 2 + …  + n ·2 / 2   =  n （ n − 1）  =  O （ n ）。所以每个Increment应该是 O （ n ），对吗？但是作业要求我证明它是 O （log n ）。我在这里做错了什么？I think the cost for n Increments should be n·2/2 + n·2/2 + n·2/2 + … +n·2/2 = n(n−1) = O(n). So each Increment should be O(n), right? But the assignment requires me to prove that it's O(log n). What have I done wrong here?推荐答案让我们拥有p位整数并遍历所有 2 ^ p 可能的值。Let we have p-bit integer and walk through all 2^p possible values.0 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1最右边的位被翻转了 2 ^ p 次（在每个步骤中），因此总成本为 2 ^ p 第二位被翻转 2 ^（p-1）次，但是成本2，因此我们的总体成本为 2 ^ p .. 最高有效位被翻转一次，但是成本 2 ^ p ，因此我们的总体成本为 2 ^ pThe rightmost bit is flipped 2^p times (at every step), so overall cost is 2^pThe second bit is flipped 2^(p-1) times but with cost 2, so we have overall cost 2^p..The most significant bit is flipped once, but with cost 2^p, so we have overall cost 2^p所有位的总和，我们对所有操作都拥有全部成本 p * 2 ^ p 。Summing costs for all bits, we have full cost p*2^p for all operations.每次操作（摊销）费用为 p * 2 ^ p / 2 ^ p = pPer-operation (amortized) cost is p*2^p / 2^p = p但请注意这是位数成本，我们必须用 N 项来表达But note this is cost in bit quantity, and we must express it in N termsN = 2^p sop = log(N)每个操作的最终摊销复杂度为 O（ log（N））Finally amortized complexity per operation is O(log(N)) 这篇关于如果现在将索引k的位翻转为2 ^ k而不是1，那么二进制计数器中的摊销分析会怎样？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！ 上岸，阿里云！