algorithm - 关于Min Max Heap DeleteMin的时间复杂度

Question

在下面关于min-max heap delete-min过程的代码片段的for循环中，为什​​么last=(*n)/2？那是因为在最坏的情况下，x 必须插入到...的孙子的孙子中，例如:树高 5:最小最大最小最大最小，floor(5/2)=2，因为在最坏的情况下，第一级之后只有两分钟。现在又一个:height 4: min max min max, floor(4/2)=2, 这次不行了。我想也许 last=(*n) 会起作用，甚至 for(i=1;;) 也会起作用，因为它只是检查不会发生的事情？题目原因是IIRC the time complexity of min-max heap deletion is
O(log n) 但 (*n)/2 让它看起来，嗯，像 O(n)。

element delete_min(element heap[], int *n) {

    int i, last, k, parent;
    element temp, x;

    if (!(*n)) {
        // checking
    }

    heap[0] = heap[1];

    x = heap[(*n)--];

    for (i=1, last=(*n)/2; i<=last; ) {
        k = min_child_grandchild(i, *n);
        if (x.key <= heap[k].key)
            break;

        heap[i] = heap[k];
        if (k <= 2*i+1) {
            i = k;
            break;
        }

        parent = k/2;
        if (x.key > heap[parent].key)
            SWAP(heap[parent], x, temp);
        i = k;
    } // end for

    heap[i] = x;

    return heap[0];
}

---

来源:

Answer 1

如果您在 n 大小范围内线性迭代，则循环执行 O(n) 次。线性在这里意味着你有一些循环索引，每次通过循环通过添加一个常量来修改它，通常但不一定是 1:

for(i = 0; i < n; i += c) { /* Loop executes O(n) times */ }

但这不是这里发生的事情。 i 没有按常量递增。它被设置为 k，其中 k 是 i 的某个子代或孙代的索引。 i 的索引最小的 child 在索引 2i 处；索引最小的孙子位于索引 4i。 (这些公式适用于基于 1 的索引，这在算法描述中很常见。)

所以循环更像这样(其中常量 c 通常为 4 但绝不会小于 2):

for(i = 0; i < n; i *= c) { /* Loop executes O(log n) times */ }