I******c
发帖数: 163 | 1 有些概念理解不了，请教一下。
我理解amortized analysis就是针对一系列操作，分析他们的平均时间复杂度。即使其
中某一个操作可能很费时，但是平均下来可能时间复杂度并不大。
但是我不理解的地方是，比如在fibonacci heap中，我们是不是也应该针对一系列操作
，计算平均时间复杂度。但是我看到书中往往拿某一个操作，比如DECREASE-KEY操作的
amortized cost和binary heap中相应操作的worst case下的时间复杂度比较。这样比
较有意义吗？如果是单纯比较某一个操作，为什么不都拿worse case下的时间复杂度进
行比较呢？
谢谢 |
S******n
发帖数: 489 | 2 我理解是大部分操作都不是worst case的。如果用worst case就不是平均时间复杂度了。
【在 I******c 的大作中提到】
: 有些概念理解不了，请教一下。
: 我理解amortized analysis就是针对一系列操作，分析他们的平均时间复杂度。即使其
: 中某一个操作可能很费时，但是平均下来可能时间复杂度并不大。
: 但是我不理解的地方是，比如在fibonacci heap中，我们是不是也应该针对一系列操作
: ，计算平均时间复杂度。但是我看到书中往往拿某一个操作，比如DECREASE-KEY操作的
: amortized cost和binary heap中相应操作的worst case下的时间复杂度比较。这样比
: 较有意义吗？如果是单纯比较某一个操作，为什么不都拿worse case下的时间复杂度进
: 行比较呢？
: 谢谢
|
l******e
发帖数: 470 | 3 中文名好象叫平摊时间复杂度。
binary heap里的worse case和amortized 没有区别
用amotized和worse比是有意义的，其实我认为amortized analysis就是更全局的worse
case analysis。
【在 I******c 的大作中提到】
: 有些概念理解不了，请教一下。
: 我理解amortized analysis就是针对一系列操作，分析他们的平均时间复杂度。即使其
: 中某一个操作可能很费时，但是平均下来可能时间复杂度并不大。
: 但是我不理解的地方是，比如在fibonacci heap中，我们是不是也应该针对一系列操作
: ，计算平均时间复杂度。但是我看到书中往往拿某一个操作，比如DECREASE-KEY操作的
: amortized cost和binary heap中相应操作的worst case下的时间复杂度比较。这样比
: 较有意义吗？如果是单纯比较某一个操作，为什么不都拿worse case下的时间复杂度进
: 行比较呢？
: 谢谢
|
P**l
发帖数: 3722 | 4 amortized analysis就是考虑的worst case吧 |
