Назовите виды алгоритмов по трудоемкости.

Изучить теоретический материал, пользуясь конспектом лекций и рекомендованной литературой.

Ответить на контрольные вопросы

Теоретические основы:

Основные термины.

Анализ алгоритма заключается в том, чтобы предсказать требуемые для его выполнения ресурсы (например, память, необходимое программное обеспечение, время работы алгоритма).

Время работы алгоритма - это число элементарных шагов, которые он выполняет.

Наихудшее время работы алгоритма - максимальное время работы из всех входных данных.

Порядок роста времени работы алгоритма – это абстрактное понятие, упрощающее анализ. Обычно один алгоритм считается эффективнее другого, если время его работы в наихудшем случае имеет более низкий порядок роста.

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

Пример.

1 алгоритм	2 алгоритм
Сортировка вставкой	Сортировка слиянием
Время работы – c1n^2, где n – количество элементов, c1 – константа, не зависящая от n	Время работы – c2nlg2n
Обычно c1 > c2
Компьютер А – выполняет 10^9 операций в секунду	Компьютер Б – выполняет 10^7 операций в секунду
Программный код записан на языке низкого уровня (c1 =2)	Программный код записан на языке высокого уровня (c2 =50)
Для сортировки миллиона команд
секунд	секунд

Понятие эффективности алгоритма.

Один из способов определения временной эффективности алгоритма заключается в следующем: на основе данного алгоритма надо написать программу и измерить время ее выполнения на определенном компьютере для выбранного множества входных данных. Хотя такой способ популярен и, безусловно, полезен, он порождает определенные проблемы. Определяемое здесь время выполнения зависит не только от используемого алгоритма, но также от архитектуры и набора внутренних инструкций данного компьютера, от качества компилятора, да и от уровня программиста, реализовавшего тестируемый алгоритм. Время выполнения также может существенно зависеть от выбранного множества тестовых входных данных. Эта зависимость становится совершенно очевидной при реализации одного и того же алгоритма с использованием различных компьютеров, различных компиляторов, при привлечении программистов разного уровня и при использовании различных тестовых входных данных. Чтобы повысить объективность оценок алгоритмов, ученые, работающие в области компьютерных наук, приняли асимптотическую временную сложность как основную меру эффективности выполнения алгоритма. Термин эффективность является синонимом этой меры и относится в основном к времени выполнения в самом худшем случае (в отличие от среднего времени выполнения).

Говорят, что алгоритм имеет эффективность (т.е. временною сложность в найхудшем случае) O(f(n)), или просто f(n), если функция от п равная максимуму числу шагов, выполняемых алгоритмом, имеет порядок роста О((n)), причем максимум берется по всем входным данным длины n. Можно сказать по-другому: существует константа с, такая, что для достаточно больших п величина cf(n) является верхней границей количества шагов, выполняемых алгоритмом для любых входных данных длины n.

Виды алгоритмов:

Алгоритмы с линейной трудоемкостью - число шагов О(n) (суммирование n элементов).

Алгоритмы с квадратичной трудоемкостью - число шагов О (n²) (если предстоит рассмотреть все варианты для выбора наиболее приемлемого – n(n-1) способы).

Алгоритмы с кубической трудоемкостью О(n³) (из набора из n попарно неравных отрезков подсчитать количество всевозможных «троек», из которых получаются невырожденные треугольники n(n-1)(n-2) вариантов).

О(n^к) - если эффективность алгоритма определяется вычислительной сложностью обработки многочлена порядка к.

Алгоритмы с полиномиальной временной сложностью О(n^к), где к – константа, которая не меняется с ростом количества элементов n.

Алгоритмы с экспоненциальной сложностью О(2ⁿ), О(n!), О(nⁿ).

Пример. Все возможные способы рассадки всех n учеников на n местах - n(n-1)(n-2)..*2*1= n!

10 учеников более 3,5 миллионов вариантов.

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

1. Метод ветвей и границ.

2. Метод частных целей (метод декомпозиции задачи и композиции решения) – разбиение сложной задачи на подзадачи.

Методы основанные на применении обоих указанных подходов относятся к так называемым точным алгоритмам, гарантирующим получение искомого решения.

Приближенные вычисления осуществляют с помощью приближенных алгоритмов (например, вычисление числа пи).

Эвристические алгоритмы – методы, позволяющие найти некоторое, заведомо неточное, но устраивающее нас решение задачи.

Контрольные вопросы:

1. В чем заключается анализ алгоритма?

2. Что такое время работы алгоритма?

3. Что собой представляет наихудшее время работы алгоритма?

4. Что собой представляет порядок роста?

5. Как определить временную эффективность алгоритма?

6. Что принято как основная мера эффективности выполнения алгоритма?

7. Что такое асимптотическая эффективность?

8. Какое обозначение дает верхнюю оценку временной трудоемкости алгоритма?

Назовите виды алгоритмов по трудоемкости.

Дата добавления: 2015-08-13