Эффективность алгоритмов. Что такое алгоритм?

1.

Эффективность алгоритмов

2.

Что такое алгоритм?
1. Алгоритм есть точное предписание, которое задает
вычислительный процесс нахождения значений вычислимой
функции по заданным значениям ее аргумента.
2. Алгоритм есть предписание, однозначно определяющее ход
некоторых конструктивных процессов.
3. Алгоритм - точное предписание, которое задает
вычислительный процесс, начинающийся с
произвольного
исходного данного и направленный на получение полностью
определенного этим исходным данным результата.
2

3.

Что такое алгоритм?
Требования для понятия АЛГОРИТМ:
1. Любой алгоритм применяется к исходным данным и выдает
результат.
2. Данные для своего размещения требуют память.
3.
Алгоритм
состоит
из
отдельных
элементарных
шагов (действий).
4. Последовательность шагов алгоритма детерминирована.
5. Каждый алгоритм должен быть результативным, т.е. после
конечного числа шагов выдавать результат.
6. Следует различать:
- описание алгоритма (инструкцию или программу);
- механизм реализации алгоритма (устройство);
- процесс реализации алгоритма.
3

4.

Что такое алгоритм?
Построение алгоритма включает
ряд следующих этапов:
1) постановка задачи;
2)
построение
математической
модели;
3) разработка алгоритма;
4)
проверка
правильности
алгоритма;
5) программирование (реализация
алгоритма);
6) анализ алгоритма и его
сложности;
7) проверка (отладка) программы;
8) составление документации.
4

5.

Принципы и способы разработки алгоритма
Системный подход – использование
методов декомпозиции (нисходящее
проектирование сверху-вниз) и синтеза
(программирование снизу-вверх).
Методы дедукции
Методы индукции: методы частных
целей, подъема, отрабатывания назад и
т.п.
Структурное
программирование:
композиция, альтернатива, итерация.
5

6.

Свойства алгоритма
Алгоритм – система формальных правил, четко и
однозначно
определяющая
процесс
решения
поставленной
задачи
в
виде
конечной
последовательности действий или операций.
6

7.

Эффективность алгоритма
Эффективность
программы
имеет
следующие
составляющие:
1. Интеллектуальная сложность
2. Пространственная эффективность (память):
определяется объемом необходимой памяти для
выполнения программы.
3. Временная эффективность сложность
быстродействие алгоритма.
Временем работы алгоритма называется
количество выполненных элементарных операций T.
Элементарные операции: запись значений в ячейку
памяти, сравнение двух значений, арифметические
операции и т.д.
Функция T(n) – Временная сложность
алгоритма.
7

8.

Эффективность алгоритма
Примеры
целтаб A[1:n]
1. Вычислить сумму первых трех элементов массива (при n≥3).
Sum:=A[1]+A[2]+A[3]
Алгоритм включает 2 операции сложения и 1 операцию записи в
память. Его сложность T(n)=3.
2. Вычислить сумму значений всех элементов массива
Sum:=0
нц для i от 1 до n
Sum:= Sum + A[i]
кц
Алгоритм включает n операций сложения и n+1 операцию
записи в память. Его сложность T(n)=n+n+1=2n+1.
8

9.

Эффективность алгоритма
Точное количество элементарных операций, затраченных для
решения конкретной задачи, зависит от размера входных данных
и от самих входных данных.
Понятие временной сложности алгоритма рассматривают в
наилучшем, наихудшем м среднем случаях. На практике основное
внимание уделяется анализу работы алгоритма в наихудшем
состоянии, так как:
1. Время работы в наихудшем случае – это верхний предел этой
величины для любых входных данных.
2. В некоторых алгоритмах наихудший случай встречается
достаточно часто.
3. Характер поведения «усредненного» времени часто не лучше
поведения времени работы наихудшего случая.
При анализе сложности алгоритма оценивают поведение
функции f(n) в пределе n→∞, т.е. скорость роста времени работы
алгоритма с увеличением размера входных данных.
Т.е. оценивается асимптотическая сложность алгоритма.
9

10.

ПРАКТИЧЕСКАЯ РАБОТА № 1
Цель работы: Выполнить анализ эмпирической
эффективности (практической сложности) методов поиска:
последовательного, быстрого последовательного, бинарного.
Методические указания по выполнению работы
Для выполнения работы необходимо:
1. Выполнить программную реализацию алгоритмов поиска.
3. Сгенерировать исходные последовательности в зависимости
от заданного размера выборки.
− для генерации исходной числовой последовательности можно
использовать датчик случайных чисел.
– для чистоты эксперимента данные должны быть из одной
сгенерированной выборки.
4. Выполнить эксперименты, в ходе которых определить время
работы каждого алгоритма в зависимости от размера выборки,
используя функцию time().
10

11.

ПРАКТИЧЕСКАЯ РАБОТА № 1
Таблица 1 – Результаты удачного поиска
Время, сек
Значение
При
При быстром
Объем выборки
При бинарном
для поиска последовательно последовательн
поиске
м поиске
ом поиске
5
10
100
250
500
600
700
800
900
Таблица 2 – Результаты неудачного поиска
Время, сек
Значение
При
При быстром
Объем выборки
При бинарном
для поиска последовательно последовательн
поиске
м поиске
ом поиске
5
10
100
250
500
600
700
800
900
11

12.

ПРАКТИЧЕСКАЯ РАБОТА № 1
5. Построить график зависимости времени работы алгоритма от
размера выборки.
6. Выполнить анализ методов и определить самый
эффективный метод в смысле быстродействия.
12

13.

ПРАКТИЧЕСКАЯ РАБОТА № 1
ПОСЛЕДОВАТЕЛЬНЫЙ ПОИСК
13

14.

ПРАКТИЧЕСКАЯ РАБОТА № 1
ПОСЛЕДОВАТЕЛЬНЫЙ ПОИСК
!
14

15.

ПРАКТИЧЕСКАЯ РАБОТА № 1
БЫСТРЫЙ ПОИСК
N
15

16.

ПРАКТИЧЕСКАЯ РАБОТА № 1
БИНАРНЫЙ ПОИСК
16