伪代码的成本常数
伪代码的成本常数
提问于 2019-12-10 08:59:31
我理解1-4、6和9-10行的成本来源。但是为什么第5行的成本是10，而第7行的成本是6呢？
Max-Heap-Increase-Key(A[1...n]: array of number, i: 1<= i <= n, key)
1 if key < A[i]
2 then print " "
3 A[i] = key
4 parent = floor(i/2)
5 while i > 1 and A[parent] < A[i]
6 temp = A[i]
7 A[i] = A[parent]
8 A[parent] = temp
9 i = parent
10 parent = floor(i/2) 每行单次执行的恒定成本如下: 1) 5，2) 1，3) 4，4) 4，5) 10，6) 4，7) 6，8) 4，9) 2，10
Count cost 1用于:读取变量，写入变量，使用数组索引定位内存位置，读取或写入数组索引，算术运算，比较(其中<=或>=计数两次)和布尔操作。
回答 1
Stack Overflow用户
发布于 2019-12-10 09:25:34
让我们看一下第5行：
while i > 1 and A[parent] < A[i]根据我们应该计算的规则：
读取变量：and.读取两次，
- 读取两次，
i读取两次，A读取一次，parent读取一次，因此一个数组有五次读操作:两次从数组读取一次>和一次<，因此有两次读取操作:一次读取
总成本是10美元。
和第7行：
A[i] = A[parent]根据规则：
- 读取变量:读取
A两次，i一次，从一个数组中读取一次:一次，在右边的数组中:一次，在左边的数组：parent。
所以总成本是6。
如果这不同于“读取或写入数组索引”，那么“使用数组索引来定位内存位置”应该是什么意思仍然是不确定的。也许这应该被计算在内，而不是加载变量A？这可能很奇怪，但将其描述为读取/写入数组的单独成本也是奇怪的。
一般来说，像A这样的变量保存一个指向数组的指针，因此访问像A[i]这样的数组需要加载该指针，然后加载索引变量，然后执行读或写操作。读或写操作将消耗前两个操作中加载的指针和索引。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/59258748
复制相关文章
相似问题
腾讯云开发者
