Нужно оценить временную сложность алгоритма.. Например для этого кода:
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.. почему надо делать именно так?
Мне чет кажется, что надо умножать среднее количество сравнений на количество просмотров? А эти данные должны как-то получаться аналитически из кода.. исходя из количества элементов массива..
..думаю мне нужен именно алгорит оценки (аналитический) на словах, на экзамене посчитать программно не получится..
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);
Конкретно в той сортировке есть два вложенных цикла 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]
Оля, andriano имел ввиду себя. Имел ввиду, что ему-то точно можно было догадаться, что здесь простой пузырь, но он поленился присмотреться.
Кстати, почему ты процитировала нас обоих (первая цитата моя, вторая - andriano) - непонятно, может, ты что-то перепутала?
Добавлено через 1 мин.
Ага, теперь, с добавленным "Ой.. действительно разные вещи.." - понятно ))