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

[Айра]

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

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]

Насколько мне известно, оценка сложности основана на количестве операций, но не воспроизводит его один к одному.
Например, если количество операций 3(n-2)(n-1) + 7(n-2)(n-1)/(4n) + 16, то сложность оценивается как O(n^2), т.е. как все младшие степени, так и коэффициент при старшей опускаются.
Кстати, в наилучшем случае сложность равна O(n), а не O(1).
А оценка для среднего случая (именно она мной и приведена) совпадает с оценкой для наихудшего и составляет O(n^2).

2klem4: Русский язык допускает неоднозначность. И фраза "Как оценить" в большинстве случаев подразумевает не алгоритм оценки, а результат.

Теперь по поводу алгоритма.
Оценить, как всегда, можно аналитически и численно. Если бы это был алгоритм (где по-русски написано, что и ЗАЧЕМ делается), то разумнее было бы оценивать аналитически. Если же есть программа, то проще, естественно, оценить численно.
В данном конкретном случае оценка проводилась по слегка измененной программе, приведенной ниже.
Количество запусков - 5: при значениях n=1000, n=1000, n=1000, n=10000 и n=100000.
Запуски 1-3 - чтобы оценить дисперсию, а 3-5 - сложность.
Т.к. использовался random, то можно считать, что эта оценка относится к среднему значению.
А оценка примерно такая: 0.45*n^2.
Количество сортируемых чисел выбиралось из следующих соображений:
- проводить оценку для единиц и десятков - бессмысленно, т.к. велика роль младших членов, поэтому 1000 - где-то минимально допустимое значение.
- чтобы оценить динамику нужно не менее 3 точек, расположенных на одинаковом расстоянии по логарифмической шкале.
- т.к. на глаз я оценил алгоритм как n^2, а мой опыт говорит, что такие алгоритмы уже при n=1000000 работают довольно долго, максимальное число составило 100000.

В принципе, можно формализовать алгоритм определения сложности и написать программу, которая будет на выходе давать именно оценку сложности, т.е. одну из строк: "O(1)", "O(log(N))", "O(N)"...

program sort_par;
const n=10000;
var m : longint;
var a: array[1..n] of integer;
    i,j,t,l: integer;
begin
  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
            inc(m);
            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);
  writeln(' ',m,' ',m/n/n:5:3);
end.