Анализ прямой вставки - PullRequest
Новая
       60

Анализ прямой вставки

0 голосов
/ 27 июня 2019

Я сейчас читаю через Н. Вирта: Алгоритмы + Структуры данных = Программы. Я не уверен, но я думаю, что в анализе предоставленной прямой вставки может быть ошибка. Снимок экрана соответствующего абзаца здесь: снимок экрана 

    type index = 0..n
    var a: array[0..n] of item

    procedure straightinsertion
        var i,j: index; x: item;
    begin
        for i := 2 to n do
        begin x := a[i]; a[0] := x; j := i-1;
            while x.key < a[j].key do
                begin a[j+1] := a[j]; j := j-1;
                end;
            a[j+1] := x
        end
    end

Я думаю, что анализ числа сравнений может быть неправильным. Он утверждает, что число C_i ключевых сравнений в i -ом сите не превышает i-1. Но не должно ли это быть i? Потому что в худшем случае, так как мы используем часовой, мы должны провести дополнительное сравнение с часовым. Я утверждаю, что:

  • C_min = n-1
  • C_ave = 1/4 * (n^2 + 3n - 4)
  • C_max = 1/2 * (n^2 + n) -1

Количество ходов M_i должно тогда быть (i-1)+2. M_min, M_ave, M_max Я полагаю, что это правильно в тексте (скриншот).

Не могли бы вы подтвердить, прав ли я или я что-то упускаю? Спасибо всем большое!

...