伪代码的成本常数

Question

我了解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）52）13）44）45）106）47）68）49）210）4

计算成本1，用于：读取变量，写入变量，使用数组索引定位内存位置，读取或写入数组索引，算术运算，比较（其中<=或> =计数两次）和布尔运算。

Answer 1

让我们看一下第5行：

while i > 1 and A[parent] < A[i]

根据我们应计数的规则：

• [读取变量： i被读取两次，A被两次读取，parent被一次读取，因此有五个读取操作。
• 从数组中读取：从数组A中两次。
• 比较：一个>和一个<，因此有两个比较。
• 布尔运算： 1 and。

总成本是10。

---

和第7行：

A[i] = A[parent]

根据规则：

• 读取变量： A读取两次，i读取一次，parent读取一次。
• 从数组中读取：一次，在右侧。
• 写入数组：一次，在左侧。

所以总成本是6。

---

仍然不确定“使用数组索引来定位内存位置”是什么意思，如果这不同于“读取或写入数组索引”。也许应该计算这个数而不是加载变量A？这将很奇怪，但是将其描述为与读取/写入数组分开的开销也很奇怪。