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

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


examination:c:question19

Вопрос №19. Анализ эффективности программы. Временная сложность.

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

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

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

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


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

Для анализа и оценки временной сложности программы необходимо знать, как часто выполняется каждая строка программы. Такая информация, полученная после выполнения программы над конкретным множеством выходных данных, называется профилем программы. Запуск программы с разными наборами входных данных дает разные профили. Концепцию профилей можно обобщить, если для каждой строки программы вывести формулу, устанавливающую соотношение между входными данными и тем, сколько раз выполняется данная строка. набор таких формул называется аналитическим профилем программы.

Построение профиля для программы Account:

Items = 3

number cost
4 50
3 25
6 30
Профиль Аналит.профиль Текст программы
10 1 1
 begin 
11 1 1
 readln(items); 
12 1 1
 cost := 0; 
13 4 n+1
 while items > 0 do 
14 3 n
 begin 
15 3 n
 items := items - 1; 
16 3 n
 readln (number, price); 
17 3 n
 cost := cost + number * price; 
18 3 n
 end; 
19 1 1
 if cost < 100 
20 0 0
 then cost := cost + lowcost 
21 1 1
 else cost := cost + highcost; 
22 1 1
 writeln (cost); 
23 1 1
 end. 

N – количество заказов.

При построении аналитического профиля программы проводится следующий анализ: напротив отдельных строк стоят конкретные числа. Это означает, что выполнение этих строк не зависит от исходных данных. остальные строки выполняются различное число раз в зависимости от исходных данных. Для построения оценки временной сложности сформируем следующую таблицу.

Аналит. профиль Условия однократного выполнения строки Общее время выполнения строки
10 1 0 0
11 1 5 5
12 1 2 2
13 n+1 2 2n+2
14 n 0 0
15 n 2 2n
16 n 10 10n
17 n 2 2n
18 n 0 0
19 1 2 2
20 0 2 0
21 1 2 2
22 1 12 12
23 1 0 0

Вывод: время выполнения данной программы имеет вид t=a*n+b, т.е. время выполнения программы прямо пропорционально количеству видов товара.


Использование условного времени выполнения несущественно. Основным является выявление характера зависимости времени выполнения программы от исходных данных. Характер зависимости времени выполнения программы от размера решаемой задачи называется временной сложностью программы и записывается в сокращенной математической форме как величина определенного порядка t: O(items).

examination/c/question19.txt · Последние изменения: 2014/01/15 08:09 (внешнее изменение)