1. Заголовок или название темы должно быть информативным ! 2. Все тексты фрагментов программ должны помещаться в теги [code] ... [/code] или [code=pas] ... [/code]. 3. Прежде чем задавать вопрос, см. "FAQ" и используйте ПОИСК ! 4.НЕ используйте форум для личного общения! 5. Самое главное - это раздел теоретический, т.е. никаких задач и программ (за исключением небольших фрагментов) - для этого есть отдельный раздел!
оценка временной сложности алгоритма, как это делать
Нужно оценить временную сложность алгоритма.. Например для этого кода:
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.
Насколько мне известно, оценка сложности основана на количестве операций, но не воспроизводит его один к одному. Например, если количество операций 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.