Методы сортировок и их реализации. Беляева И.В - 9 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

Что
конкретно
нужно
знать
о
быстродействии
алгоритма?
Важнее
всего
знать,
насколько
быстро
возрастает
время
его
выполнения
с
увеличением
размера
задачи.
Степень
роста
временных
затрат
(growth
rate)
выражается
следующими
высказываниями.
2
Время
выполнения
алгоритма
А
прямо
пропорционально
п
.
Время
выполнения
алгоритма
В
прямо
пропорционально
n
По
этим
утверждениям
нельзя
определить,
сколько
именно
времени
выполняется
алгоритм
А
или
В.
Главное,
что
при
решении
больших
задач
алгоритм
В
работает
намного
быстрее.
Иными
словами,
объем
времени,
затрачиваемый
алгоритмом
В,
выраженный
функцией,
зависящей
от
размера
задачи,
растет
медленнее,
чем
время
выполнения
алгоритма
А,
поскольку
линейная
функция
растет
медленнее
квадратичной.
Даже
если
В
действительно
затрачивает
5 * n
секунд,
в
то
время
как
алгоритм
А
выполняется
за
n
2
/5
секунд,
в
целом
алгоритм
В
выполняется
значительно
быстрее
алгоритма
А.
Эта
ситуация
проиллюстрирована
на
рис.
1.
Таким
образом,
выражение
Время
выполнения
алгоритма
А
прямо
пропорционально
n
2
точно
характеризует
эффективность
алгоритма
и не
зависит
от
конкретных
компьютеров
и
реализаций.
Алгоритм
А
выполняется
за
п2/5
секунд
Алгоритм
В
выполняется
за
5*п
секунд
25
n
РИСУНОК
1.
Время
выполиения
алгоритмов
как
функция,
зависящая
от
размера
задачи
n
Оценка
порядка
величины
и
обозначение
О-большое
Допустим,
выполняется
следующее
утверждение.
Время
выполнения
алгоритма
А
прямо
пропорционально
функции
f(n}.
В
таких
случаях
говорят,
что
алгоритм
А
имеет
порядок
f(n}
(order f(n)).
Этот
факт
обозначается
как
О
(f(n)).
Функция
f(n)
называется
сложностью
алгоритма
(growth-rate function).
Поскольку
в
обозначении
используется
прописная
буква
О
(первая
буква
слова
опаее
(порядок)),
оно
называется
обозначением
О-большое
(Big-O notation).
8

Страницы