VPF::Экпрериметальная оценка сложности алгоритма

bullvinkle

Дата 24.12.2008, 16:37 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 52
Регистрация: 18.3.2008

Репутация: нет
Всего: нет

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

Код


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.

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

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

Это сообщение отредактировал(а) bullvinkle - 24.12.2008, 16:38

maxdiver

Дата 24.12.2008, 16:55 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 381
Регистрация: 29.1.2008
Где: Саратов

Репутация: 16
Всего: 18

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

Однако у вас тема называется "экспериментальная", что немного отличается от "теоретической" оценки smile

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

bullvinkle

Дата 24.12.2008, 23:24 (ссылка)

(нет голосов)

Загрузка ...

Шустрый

Профиль
Группа: Участник
Сообщений: 52
Регистрация: 18.3.2008

Репутация: нет
Всего: нет

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

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Алгоритмы \| Следующая тема »