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.
Конкретно в той сортировке есть два вложенных цикла 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).