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

[Айра]

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

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.

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

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

[Michael_Rybak]

давай возьмем, давай

сразу разбиваем на последовательные блоки:

блок номер раз:

  i:=0;
  l:=0;
  randomize;
  m := 0;

блок номер два:

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);

В блоке номер раз все выполняется за константное время. Константное относительно n. Смысл этой фразы в том, что при увеличении n время выполнения блока номер раз никак не увеличится.

Таким образом, сложность первого куска равна O(1). Пишут единичку, потому что единичка никак не поменяется при увеличении n.

В блоке номер два у нас циклы. Смотрим первый цикл. Одно действие (тело цикла) выполняется внутри другого (итерации цикла). Цикл выполняется n раз, значит сложность тела цикла нужно умножить на n. Как мы уже умеем определять, тело цикла имеет сложность O(1). Таким образом, сложность цикла - O(n).

Второй цикл такой же.

Сложность двух последовательных кусков, сложность каждого из которых равна O(n), тоже равна O(n).

В блоке номер три у нас кривые руки. Мы зачем-то дико замаскировали самый банальный пузырек, проверяя то четные, то нечетные пары. Ну ок.

Тут уже нужно включать аналитическую часть ума, и понимать, что в худшем случае вся эта байда (внешний while) выполнится n раз (можно оценивать и сложность в среднем, а не худшем случае, но исторически сложилось, что в computer science по умолчанию подразумевают сложность именно в худшем случае). Сложность тела while равна O(n), и таким образом, сложность третьего блока - O(n^2).

Блок номер 4 у нас O(n).

Таким образом имеем O(1), O(n), O(n^2) и O(n). Общая сложность O(n^2).

Вообще, самый простой способ понять, что такое сложность - это функция, которая показывает, во сколько раз дольше будет работать программа, если размер входных данных увеличится во столько-то раз.

К примеру, линейная сложность, O(n), означает, что если n будет в два раза больше, то и программа будет работать примерно в два раза больше. А сложность O(2^n) означает, что если n будет на 1 больше, программа будет работать на порядок дольше.

Именно поэтому коэффициенты можно игнорировать.

Конечно, всё это здесь неформально. На самом деле O(f(n)) - математический термин, и формулируется он в терминах пределов при n стремящемся к бесконечности. Но нам, нормальным людям, это ни к чему.