Невозможно отобразить презентацию
ИнформатикаПохожие презентации:
Алгоритмы и анализ сложности
Алгоритмы и анализ сложности Институт Информационных Технологий ЧелГУ, 20101 Лекция 1.
Основные понятия.2А лгоритм .
Основные понятия.
Рецепт Процесс Алгоритм Метод Способ Процедура Конечность Определенность Ввод Вывод Эффективность Алгоритм - это точный набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное время.3А лгоритм .
Основные понятия.
Конечность .
Алгоритм всегда должен заканчиваться после конечного числа шагов.
Количество шагов может быть сколько угодно большим, но для определенных входных данных их число ограничено Сортировка массива из100 элементов Не более 10000 шагов Сортировка массива из 1000 элементов Не более 1000000 шагов4А лгоритм .
Основные понятия.
Определенность .
Каждый шаг алгоритма должен быть точно определен.
Начало Ввод A,B C=A/B Вывод С Конец Что делать, если A не делится на B нацело? Сколько знаков после запятой нужно вывести?5А лгоритм .
Основные понятия.
Ввод .
Алгоритм имеет некоторое число входных данных.
Эти данные берутся из определенного набора объектов Вывод .
У алгоритма есть одно или несколько выходных данных, то есть величин, имеющих вполне определенную связь с входными данными.
Пример.
Алгоритм сортировки массива: Ввод : массив из n чисел Вывод : массив из n чисел6А лгоритм .
Основные понятия.
Эффективность .
Алгоритм считается эффективным, если все его операторы достаточно просты для того, чтобы их можно было точно выполнить в течение конечного промежутка времени.7 Анализ сложности алгоритмов Анализ сложности необходим для получения оценок или границ для объема памяти и времени работы, необходимых алгоритму для успешной обработки входных данных.
Количество элементарных операций, затраченных алгоритмом для решения конкретного экземпляра задачи, зависит не только от размера входных данных, но и от самих данных.
Сколько времени нужно алгоритму для выполнения? Сколько ресурсов ( памяти) нужно алгоритму для выполнения? Время работы алгоритма зависит
• От размера входных данных
• От самих данных8 Анализ сложности алгоритмов Временная сложность алгоритма в худшем случае — это функция размера входных и выходных данных, равная максимальному количеству элементарных операций, проделываемых алгоритмом для решения экземпляра задачи указанного размера.
Временная сложность алгоритма в наилучшем случае — это функция размера входных и выходных данных, равная минимальному количеству элементарных операций, проделываемых алгоритмом для решения экземпляра задачи указанного размера.9 Анализ сложности алгоритмов Пример .
Алгоритм нахождения минимального элемента массива A из n элементов.
min=A[0];
for(i=1;i<n;i++){ if(A[i]<min) min=A[i];}n – размер входных данных Элементарными операциями будем считать сравнение текущего элемента с минимальным “ if(A[i]<min) ” и присвоение переменной min значения A[i] “ min=A[i];” Временная сложность алгоритма в наилучшем случае –n Пример входных данных: (1,4,6,8,2,5) Временная сложность алгоритма в худшем случае – ( n-1)*2+1 Пример входных данных: (8,6,5,4,2,1)10 f(n) ограничена сверху функцией g(n) (с точностью до постоянного множителя) асимптотически Анализ сложности алгоритмов В большинстве случаев временная сложность алгоритма не может быть определена точно.
Поэтому чаще всего используют понятие асимптотической сложности алгоритма.
Для оценки сложности алгоритма используется символO Запись вида f(n) = O(g(n)) означает, что ф-ия f(n) возрастает медленнее чем ф- ия g(n) при с = с1 и n = N, где c1 и N могут быть сколь угодно большими числами, т.е.
При c = c1 и n >= N, c*g(n) >=f(n) (А).
Оценка АС решает задачу масштабируемости данных, т.е.
как влияет увеличение объема входных данных на увеличение времени работы алгоритма.12 Анализ сложности алгоритмов Пример .
Алгоритм нахождения минимального элемента массива A из n элементов.
min=A[0];
for(i=1;i<n;i++){ if(A[i]<min) min=A[i];} Временная сложность алгоритма в наилучшем случае –n Пример входных данных: (1,4,6,8,2,5) Временная сложность алгоритма в худшем случае – f(n)=( n-1)*2+1=2n-1 Пример входных данных: (8,6,5,4,2,1) Асимптотическая сложность алгоритма - O(n) с=2, 2n-1<2n13 № п.п.(От сложного к простому) Название сложности Мат.
формула Примеры алгоритмов 1 ФакториальнаяN! Алгоритмы комбинаторики (сочетания, перестановки и т.д.) 2 Экспоненциальная KN Алгоритмы перебора( brute force) 3 Полиномиальная NK Алгоритмы простой сортировки ( buble sort) 4 Линейный логарифм N * log(N) Алгоритмы быстрой сортировки ( heap sort) 5 Линейная K * N Перебор элементов массива 6 Логарифмическая K * log(N) Бинарный поиск 7 КонстантнаяК Обращение к элементу массива по индексу14 Классы опорных функции
• f(n) = O(1) константа f(n) = O(log(n)) логарифмический рост f(n) = O(n) линейный рост f(n) = O(n*log(n)) квазилинейный рост f(n) = O(n^m) полиномиальный рост f(n) = O(2^n) экспоненциальный рост Увеличение объема данных Увеличение времени15 Примеры экспоненциальный рост логарифмический рост и линейный рост16 Заключение
• Анализ сложности необходим для того, чтобы оценит как влияет увеличение объема входных данных на время выполнения
Основные понятия.2А лгоритм .
Основные понятия.
Рецепт Процесс Алгоритм Метод Способ Процедура Конечность Определенность Ввод Вывод Эффективность Алгоритм - это точный набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное время.3А лгоритм .
Основные понятия.
Конечность .
Алгоритм всегда должен заканчиваться после конечного числа шагов.
Количество шагов может быть сколько угодно большим, но для определенных входных данных их число ограничено Сортировка массива из100 элементов Не более 10000 шагов Сортировка массива из 1000 элементов Не более 1000000 шагов4А лгоритм .
Основные понятия.
Определенность .
Каждый шаг алгоритма должен быть точно определен.
Начало Ввод A,B C=A/B Вывод С Конец Что делать, если A не делится на B нацело? Сколько знаков после запятой нужно вывести?5А лгоритм .
Основные понятия.
Ввод .
Алгоритм имеет некоторое число входных данных.
Эти данные берутся из определенного набора объектов Вывод .
У алгоритма есть одно или несколько выходных данных, то есть величин, имеющих вполне определенную связь с входными данными.
Пример.
Алгоритм сортировки массива: Ввод : массив из n чисел Вывод : массив из n чисел6А лгоритм .
Основные понятия.
Эффективность .
Алгоритм считается эффективным, если все его операторы достаточно просты для того, чтобы их можно было точно выполнить в течение конечного промежутка времени.7 Анализ сложности алгоритмов Анализ сложности необходим для получения оценок или границ для объема памяти и времени работы, необходимых алгоритму для успешной обработки входных данных.
Количество элементарных операций, затраченных алгоритмом для решения конкретного экземпляра задачи, зависит не только от размера входных данных, но и от самих данных.
Сколько времени нужно алгоритму для выполнения? Сколько ресурсов ( памяти) нужно алгоритму для выполнения? Время работы алгоритма зависит
• От размера входных данных
• От самих данных8 Анализ сложности алгоритмов Временная сложность алгоритма в худшем случае — это функция размера входных и выходных данных, равная максимальному количеству элементарных операций, проделываемых алгоритмом для решения экземпляра задачи указанного размера.
Временная сложность алгоритма в наилучшем случае — это функция размера входных и выходных данных, равная минимальному количеству элементарных операций, проделываемых алгоритмом для решения экземпляра задачи указанного размера.9 Анализ сложности алгоритмов Пример .
Алгоритм нахождения минимального элемента массива A из n элементов.
min=A[0];
for(i=1;i<n;i++){ if(A[i]<min) min=A[i];}n – размер входных данных Элементарными операциями будем считать сравнение текущего элемента с минимальным “ if(A[i]<min) ” и присвоение переменной min значения A[i] “ min=A[i];” Временная сложность алгоритма в наилучшем случае –n Пример входных данных: (1,4,6,8,2,5) Временная сложность алгоритма в худшем случае – ( n-1)*2+1 Пример входных данных: (8,6,5,4,2,1)10 f(n) ограничена сверху функцией g(n) (с точностью до постоянного множителя) асимптотически Анализ сложности алгоритмов В большинстве случаев временная сложность алгоритма не может быть определена точно.
Поэтому чаще всего используют понятие асимптотической сложности алгоритма.
Для оценки сложности алгоритма используется символO Запись вида f(n) = O(g(n)) означает, что ф-ия f(n) возрастает медленнее чем ф- ия g(n) при с = с1 и n = N, где c1 и N могут быть сколь угодно большими числами, т.е.
При c = c1 и n >= N, c*g(n) >=f(n) (А).
Оценка АС решает задачу масштабируемости данных, т.е.
как влияет увеличение объема входных данных на увеличение времени работы алгоритма.12 Анализ сложности алгоритмов Пример .
Алгоритм нахождения минимального элемента массива A из n элементов.
min=A[0];
for(i=1;i<n;i++){ if(A[i]<min) min=A[i];} Временная сложность алгоритма в наилучшем случае –n Пример входных данных: (1,4,6,8,2,5) Временная сложность алгоритма в худшем случае – f(n)=( n-1)*2+1=2n-1 Пример входных данных: (8,6,5,4,2,1) Асимптотическая сложность алгоритма - O(n) с=2, 2n-1<2n13 № п.п.(От сложного к простому) Название сложности Мат.
формула Примеры алгоритмов 1 ФакториальнаяN! Алгоритмы комбинаторики (сочетания, перестановки и т.д.) 2 Экспоненциальная KN Алгоритмы перебора( brute force) 3 Полиномиальная NK Алгоритмы простой сортировки ( buble sort) 4 Линейный логарифм N * log(N) Алгоритмы быстрой сортировки ( heap sort) 5 Линейная K * N Перебор элементов массива 6 Логарифмическая K * log(N) Бинарный поиск 7 КонстантнаяК Обращение к элементу массива по индексу14 Классы опорных функции
• f(n) = O(1) константа f(n) = O(log(n)) логарифмический рост f(n) = O(n) линейный рост f(n) = O(n*log(n)) квазилинейный рост f(n) = O(n^m) полиномиальный рост f(n) = O(2^n) экспоненциальный рост Увеличение объема данных Увеличение времени15 Примеры экспоненциальный рост логарифмический рост и линейный рост16 Заключение
• Анализ сложности необходим для того, чтобы оценит как влияет увеличение объема входных данных на время выполнения