个人中心
文章发布
退出
作者热门文章
- iOS/Objective-C 元类和类别
- objective-c - -1001 错误，当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
25
4
我已经阅读了一些关于摊销分析的帖子，但我在理解潜在方法方面仍有一些疑问>.
主要问题在于如何开发形式化的势函数？以及如何评估势函数的正确性？
比如有一道题:
A sequence of n operations is performed on a data structure. The ith operation costs i if i is an exact power of 2, and 1 otherwise. Use a potential method to determine the amortized cost per operation.
采用势函数，首先要提出一个势函数: 
.有人告诉我这很直观，但几个小时后我还是想不出来......
我发现有一个类似的问题:
need to find the amortized cost of a sequence using the potential function method
不过，我认为答案是关于帐户方法。
最佳答案
提示:
每次 k 增加时，项 k 都会增加(很明显)，它增加了 1。
每当 k 达到 2 的新次方时，2^ceiling(Lg(k)) 项就会增加，它增加了i/2.
关于algorithm - 如何在摊销分析中提出潜在的功能？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/26544810/
25
4
0
我只是想在继续之前向某人确认我走在正确的轨道上。问题指出，当我想向已经满的数组添加新元素时，我必须“在 O(1)(amortized) 中扩展数组”。 这是不是说每次我将一个新元素插入到完整列表中时，
我试图从复杂性的角度更好地理解哈希表和字典在 C# 中的工作方式(但我想语言不是一个重要因素，这可能只是一个理论问题)。 我知道如果 Count 小于容量(这有点明显)。 不过，让我们看看这段代码:
我是一名优秀的程序员,十分优秀！