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

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.

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

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

O(n^2)

andriano, помоему вопрос был поставлен достаточно четко: ?

у меня получилось, что в лучшем случае (массив уже отсортирован) - 2 (количество просмотров массива)
а в худшем (отсортирован в обратном порядке) n\2*(n+2), где n\2 - среднее количество сравнений (смущает меня эта переменная), а n+2 - кол-во просмотров.. Максимальная величина получается порядка О(n^2).. но по идее надо среднюю величину чтоли вычислять?

Насколько мне известно, оценка сложности основана на количестве операций, но не воспроизводит его один к одному.
Например, если количество операций 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.

оффтоп



Согласен, только в посте Айры такой фразы нет.

в продолжение оффтопа: была фраза "как это сделать".. думаю она трактуется однозначно))))

и все таки, я не понимаю _как_ Мы посчитали количество сравнений, а затем поделили его на n^2.. почему надо делать именно так?
Мне чет кажется, что надо умножать среднее количество сравнений на количество просмотров? А эти данные должны как-то получаться аналитически из кода.. исходя из количества элементов массива..

..думаю мне нужен именно алгорит оценки (аналитический) на словах, на экзамене посчитать программно не получится..

Исключительно для иллюстрации, что мы угадали.
На самом деле можно написать программу, которая сама определяет, какой сложности алгоритм используется.
В приведенном ниже примере подай на вход упорядоченную последовательность, например, так:

for i:=1 to n[j] do b[i]:=i;

для того, чтобы убедиться, что программа вернор определяет сложность хотя бы в этих двух (упорядоченный и не упорядоченный массив) случаях.

program sort_par;

type MyArray = array[1..100000] of integer;
var b : MyArray;

function TestSort(var a : MyArray; n : longint): longint; // Returns amount of passes of an internal cycle
var m,l,j,i,t : longint;
begin
  j := 0;
  l := 0;
  m := 0;
  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;
  TestSort := m;
end;

const
  n : array[0..1]of longint = (1000, 10000); // array length
  o : array[0..6]of string = ('1','log(N)','N','N*log(N)','N^2','N^2*log(N)','N^3');
var
  i,j : longint;
  m : array[0..1]of longint;     // amount of passes
  k : array[0..6]of double;  // Statistics // 0 - const, 1 - log, 2 - n, 3 - n*log, 4 - n^2, 5 - n^2*log, 6 - n^3
  delta : double;
  choice : longint;
begin
  randomize;
  for j := 0 to 1 do begin;
    for i:=1 to n[j] do b[i]:=random(32766)-16383;
    m[j] := TestSort(b, n[j]);
//    writeln(j,' ',n[j]:6,' ',m[j]:9);
  end;
  k[0] := (m[1]/m[0]);
  k[1] := (m[1]/m[0])/ln(n[1]/n[0]);
  k[2] := (m[1]/m[0])/(n[1]/n[0]);
  k[3] := (m[1]/m[0])/(n[1]/n[0])/ln(n[1]/n[0]);
  k[4] := (m[1]/m[0])/sqr(n[1]/n[0]);
  k[5] := (m[1]/m[0])/sqr(n[1]/n[0])/ln(n[1]/n[0]);
  k[6] := (m[1]/m[0])/sqr(n[1]/n[0])/(n[1]/n[0]);
//  for i := 0 to 6 do
//    writeln(k[i]:5:3);
  delta := 1.0e+30;
  choice := -1;
  for i := 0 to 6 do begin
    if delta > abs(1.0-k[i]) then begin
      delta := abs(1.0-k[i]);
      choice := i;
    end;
  end;
//  for i:=1 to n[j] do write(b[i]:4);
  if choice <> -1 then
    writeln('O(',o[choice],') Algorithm')
  else
    writeln('Unknown');
end.

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

Эх.. вернемся к нашим баранам..
Как оценивать временную сложность? (нужен алгоритм на словах..) Как глядя на код, не прибегая ни к каким дополнительным средствам оценить ее?..

1) выделить переменные, относительно которых считается сложность
2) если два действия выполняются по очереди, берется максимум сложностей
3) если два действия выполняются одно внутри другого, сложности умножаются
4) числовые коэффициенты и свободные члены можно опускать
5) вообще, в многочлене можно оставлять старший член

вообще, гораааздо легче на примерах. и показывать, и понимать.

Спасибо! А если в качестве примера взять ту сортировку, что в первом посте?

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

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

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

  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 стремящемся к бесконечности. Но нам, нормальным людям, это ни к чему.

Конкретно в той сортировке есть два вложенных цикла 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, минимальным анализом там видно, что внешний цикл это просто условие "пока массив не отсортирован". это обычный пузырь.

Ну не узнал я этого "простого пузыря" (и сейчас не узнаю), но по поведению (~(N^2)/2) очень похож.

Смотри, там l (маленькое L) - переменная, обозначающая, какие пары мы сейчас проверяем - четные, или нечетные.

Когда l = 1, проверяются пары элементов на позициях вида (2k + 1, 2k + 2). Когда l = 0 - позиции вида (2k, 2k + 1). Если в какой-то паре числа стоят в неправильном порядке (убывания) - числа в паре меняются местами, а счетчик l сбрасывается (опять начинаем с проверки пар вида (2k, 2k + 1)).

У меня не кривые руки.. нам на лекциях эту сортировку дали..

Значит надо рассматривать именно худший вариант. И, в принципе, я поняла как это делать.. Спасибо большое!!


[offtop] честно, я даже и не думала, что на этом форуме могут возникнуть проблемы с пониманием того, что происходит в конкретном коде [/offtop]

Добавлено через 5 мин.

Даже несколько проще (или просто другими словами))) l-ка увеличивается, когда нет замен, а если они есть, то сбрасывается.. даже в лучшем случае должно быть два просмотра, а тогда l будет равно 2..

[offtop]Проблемы не с пониманием, проблемы с банальной ленью. [/offtop]

Я рассчитывал на то, что ты поймешь, что я имею ввиду, что руки кривые - не у тебя, а у видного маскировщика пузырьковых сортировок, родившего сие (я почему-то верил, что это - не ты).



А вот всегда пожалуйста



Это не другими словами, и не несколько проще - это разные аспекты. Я описал, в чем смысл переменной l, а ты - как он достигается.

Ой.. действительно разные вещи..


Хм.. а в чем она по твоему выражается?.. В том, что я не описываю алгоритм по вполне объяснимым причинам (1. на экзамене у меня будет только код, без словесного описания.. 2. я не думаю, что _здесь_ кто-то не может сам понять код), или кому-то просто лень самому подумать? Тем более, что такого сложного в этом коде, что его весь нужно комментировать?..

Оля, andriano имел ввиду себя. Имел ввиду, что ему-то точно можно было догадаться, что здесь простой пузырь, но он поленился присмотреться.

Кстати, почему ты процитировала нас обоих (первая цитата моя, вторая - andriano) - непонятно, может, ты что-то перепутала?

Добавлено через 1 мин.
Ага, теперь, с добавленным "Ой.. действительно разные вещи.." - понятно ))