оценка временной сложности алгоритма, как это делать Опции

[Айра]

Нужно оценить временную сложность алгоритма.. Например для этого кода:

program sort_par;
const n=10;
var a: array[1..n] of integer;
    i,j,t,l: integer;
begin
  i:=0;
  l:=0;
  randomize;
  for i:=1 to n do a[i]:=random(11)-5;
  for i:=1 to n do write(a[i]:4);
  writeln;
  while l<>2 do
    begin
      inc(l);
      inc(j);
      i:=2-(j mod 2);
        while i<n-1+(j mod 2) do
          begin
            if a[i]>a[i+1] then
              begin
                l:=0;
                t:=a[i];
                a[i]:=a[i+1];
                a[i+1]:=t;
              end;
            inc(i,2);
          end;
    end;
  for i:=1 to n do write(a[i]:4);
end.

Подскажите как это правильно сделать?

Заранее, спасибо))

[andriano]

Конкретно в той сортировке есть два вложенных цикла while, откуда можно сделать вывод, что сложность не превышает O(N^2). Во внутреннем цикле перебор идет по i, причем i инкрементируется, т.е. сложность внутренего цикла O(N). Сложность внешнего цикла мне лично оценить труднее - ну не вижу я здесь явной переменной, по которой идет перебор, а комментарии, которые могли бы прояснить, что же автор этого кода хотел сказать, здесь почему-то отсутствуют. Но, в сущности, выбор невелик: это либо O(log(N)), либо O(N). При этом первый вариант менее вероятен, т.к. я нигде не увидел характерного для алгоритмов сложности O(log(N)) действия - деления интервала на 2 (бывает и по золотому сечению). Поэтому беглый осмотр приводит к выводу, что алгоритм похож на O(N^2).
Собственно, это предположение я и подтвердил программно (поэтому в моем первом исходнике я и делил на n^2).

PS. Да, на остальные циклы можно внимания не обращать, т.к. у них сложность O(N).

Сообщение отредактировано: andriano - 21.03.2008 18:40