Инструменты пользователя

Инструменты сайта


examination:c:question20

Билет №20. Анализ эффективности программы. Объемная сложность.

Анализ и оценка эффективности программ

Программа считается эффективной, если она производит вычисления максимально быстро и при этом занимает минимальный объем памяти. На практике эти критерии являются взаимообратными. Для ускорения вычислений требуется использование большего объема памяти и наоборот.

Каждый из этих критериев может быть оценен с помощью следующих характеристик:

  1. Время выполнения программы( посредством выполнения временной сложности программы )
  2. Объем занимаемой памяти( посредством вычисления объемной сложности программы )


Анализ объемной сложности программы

Во время работы программы ОЗУ занята командами программы и внутренними данными, с которыми оперирует программа. При изучении эффективности программы важен объем памяти, занятый данными. В структурных языках число одновременно существующих переменных меняется в течение работы программы. Следовательно, представляет интерес оценка максимального объема памяти, занимаемого данными. Эта оценка называется объемной сложностью программы. Как и временная сложность, объемная выражается через несколько величин, отражающих размер решаемой задачи.


Алгоритм вычисления объемной сложности:

  1. Записывается схема вызова программы
  2. Каждой строке схемы вызовов сопоставляются возникающие параметры(глобальные и локальные переменные и объем памяти для каждой из них)
  3. На основании этой информации определяется место или места в программе, в которых параметры и переменные занимают наибольший объем памяти

Рассмотрим пример:

Program Calculator;
Var a,b : real; c : char;
 
Procedure Add (a,b);
Var s:real;
Begin
	s:=a+b;
End.
 
Procedure subs(a,b);
Var s:real;
Begin
	s:=a-b;
End.
 
Function Fact (x:real);
Var i:integer;
Begin
	For i:=1 to 10 do
	x:=x*x;
	Fact:=x;
End.
 
Begin
	Writeln(‘Введите операцию’);
	Readln(c);
	Case c of+: Add (a,b);-: subs (a,b);
	‘!’ : Fact (a.b);
End.
Схема вызова Новые данные Использованная память
Calculator a (6b), b (6b), c (1b) 13b
Add s (6b) 19 b
Subs s (6b) 19 b
Fact x (4b) 27 b

Из таблицы видно, что данные занимают наибольший объем при выполнении функции Fact. Так как объем памяти не зависит от исходных данных, то объемная сложность будет О(1) – порядка 1.


Способы повышения эффективности программы:

  • Выбор алгоритма (выбор правильного алгоритма является одним из ключевых моментов оптимизации времени выполнения программы, кроме того может влиять и на объемную сложность)

Пример:

//Рассмотрим 2 функции нахождения наибольшего общего делителя двух положительных чисел
function NOD (a,b:integer) : integer;
begin
	while a<>b do
		if a>b
		then a:-a-b
		else b:=b-a;
	NOD:=a;
end.
 
function NOD (a,b : integer) : integer;
var r:integer;
begin
	repeat r:=a mod b;
	a:=b;
	b:=r;
	until b=0;
	NOD:=a;
end. 
Операция 1 алгоритм 2 алгоритм
<> 9 1
:= 5 4
+ 4 0
* 0 1
18 6
  • Сокращение накладных расходов (при реализации алгоритма различают операторы, управляющие вычислениями, и непосредственно вычисляющие операторы. Операторы , участвующие только в выполнении вычислений рассматриваются как накладные расходы. Примерами могут быть условные выражения, управляющие циклами. Комбинации операторов, используемые всеми частями программы для работы с фрагментами, содержащими накладные расходы)<code>

Пример:

Вычислим разложение функции sinx в ряд Тейлора с заданной точностью e.

Таким образом, для эффективного метода вычисления необходимо произвести математические преобразования для реорганизации или упрощения формул.


FIXME В КОНСПЕКТЕ РИСУНОК! (22):!:

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


При повышении эффективности программы необходимо учитывать:

  1. Внесение изменений в программу может привести к появлению ошибок. Вследствие чего, эти изменения надо вносить с особой аккуратностью.
  2. Понятность алгоритма является более значимым критерием эффективности алгоритма.
examination/c/question20.txt · Последние изменения: 2014/01/15 12:09 (внешнее изменение)