О временной сложности Min Max Heap DeleteMin - PullRequest
Новая
       46

О временной сложности Min Max Heap DeleteMin

0 голосов
/ 22 декабря 2018

В цикле for следующего фрагмента кода процедура min-max heap delete-min, почему last=(*n)/2?Это потому, что в худшем случае, что х должен быть вставлен внуку внука ..., и, например: высота дерева 5: min max min max min, floor (5/2) = 2, правильно св худшем случае всего лишь две минуты после первого уровня.Теперь еще один: высота 4: мин макс мин макс, этаж (4/2) = 2, на этот раз это не работает.Я думаю, что last=(*n) будет работать, и даже for(i=1;;) будет работать, поскольку он просто проверяет что-то, что не произойдет?Причина этого названия в том, что во IIRC временная сложность удаления кучи min-max составляет
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];
}

источник:

enter image description here

1 Ответ

0 голосов
/ 23 декабря 2018

Если вы выполняете линейную итерацию в диапазоне размеров n, цикл выполняется O (n) раз.Линейно здесь означает, что у вас есть некоторый индекс цикла, который изменяется каждый раз через цикл путем добавления константы, обычно, но не обязательно 1: 

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

Но это не то, что здесь происходит.i не увеличивается на постоянную.Он устанавливается на k, где k - это индекс какого-либо ребенка или внука i.Дочерний элемент i с наименьшим индексом имеет индекс 2i;внук, чей индекс наименьший, имеет индекс 4i.(Эти формулы для индексов на основе 1, которые являются общими в описаниях алгоритмов.)

Таким образом, цикл больше похож на этот (где константа c обычно равна 4, но никогда не меньше 2): 

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