Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате
Форум программистов > Алгоритмы > Экпрериметальная оценка сложности алгоритма


Автор: bullvinkle 24.12.2008, 16:37
Помогите оценить сложность алгоритма.
Мы этого не учили, но в индивидуальном задании это требуется (объясняется типа "на то оно и индивидуальное, что бы сами что то выучили").
Вобщем есть у меня алгоритм сортировки методом Хоара.
Вот так я его реализовал
Код

type words = record
       number: word;
       word: string[20];
  end;
var  T:words;
     a: array [1..2700] of words;
     f1,f2,f3:text;
     ch:char;
     s,str1, str2, min: string;
     c,n,p,kol,ww,q, imin:integer;
{==========================Процедура сортировки=====================}
procedure hoar (l,r:word);
var
   b,tmp:string;
   i,j,ntmp:word;
begin
     b:=a[(l+r) div 2].word;
     i:=l;j:=r;
     while i<=j do begin
           while a[i].word < b do inc(i);
           while a[j].word > b do dec(j);
           if i<=j then begin
              tmp:=a[i].word;
              ntmp:=a[i].number;
              a[i].word:=a[j].word;
              a[i].number:=a[j].number;
              a[j].word:=tmp;
              a[j].number:=ntmp;
              inc(i);
              dec(j);
              end;
              end;
      if l<j then hoar (l,j);
      if i<r then hoar (i,r);
end;
{===================================================================}
BEGIN
assign(f2, 'd:\2.txt');
reset(f2);
assign(f3, 'd:3.txt');
rewrite(f3);
s:='';
p:=0;
{======================Заносим слова в массив============================}

 while not eof(f2) do begin
 readln(f2,s);
 inc(p);
 a[p].word:=s;
 a[p].number:=p;
 end;
{=====================Сортировка=========================================}
 kol:=p;
hoar(1,kol);
{===============================Вывод====================================}
for p:=1 to kol do writeln(f3,a[p].word,'   ',a[p].number);

close(f2);
close(f3);
  END.

Сортирую строки в файле.

Идеально, конечно же, было бы если бы мне кто то проанализировал и посчитал выч. сложность, но если это слишком трудоемкая работа, то попрошу посоветовать мне литературу, что бы я сам разобрался.

Автор: maxdiver 24.12.2008, 16:55
Теоретическая оценка быстрой сортировки (что N^2 в худшем случае, и NlogN в среднем) встречается в каждой второй книге по алгоритмам smile

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

Автор: bullvinkle 24.12.2008, 23:24
Спасибо, Вам большое, что уберегли меня от дурной работы.
Ну все, буду ганять функцию gettime, которая оч. корявая)))

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)