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

UptoLike

ВУЗ: 

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

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

Рубрика: 

п
Время
выполнения
линейного
алгоритма
(linear
algorithm)
прямо
пропорционально
размеру
задачи.
Если
размер
задачи
возводится
в
квадрат,
объем
времени
увеличивается
точно
так
же
n*log
2n
Время
выполнения
алгоритма,
имеющего
сложность
O(n*log2n)
растет
быстрее,
чем
у
линейного
алгоритма.
Такие
алгоритмы
обычно
разбивают
задачи
на
подзадачи
и
решают
их
по
отдельности.
Пример
такого
алгоритма
-
сортировка
слиянием
-
рассматривается
далее
2
n
Время
выполнения
квадратичного
алгоритма
(
quadratic
аlgогithm)быстро
возрастает
с
увеличением
размера
задачи.
В
алгоритмах
такого
типа
часто
используются
два
вложенных
цикла.
Такие
алгоритмы
следует
применять
лишь
для
решения
небольших
задач.
n
3
Время
выполнения
кубического
алгоритма
(qubic algorithm)
еще
быстрее
возрастает
с
увеличением
размера
задачи
по
сравнению
с
квадратичным.
Алгоритмы,
использующие
три
вложенных
цикла,
часто
оказываются
кубическими.
Такие
алгоритмы
следует
при
менять
лишь
для
решения
небольших
задач
2
n
С
увеличением
размера
задачи
время
выполнения
экспоненциального
алгоритма
(exponential algorithm)
обычно
резко
возрастает,
поэтому
на
практике
такие
алгоритмы
при
меняются
редко
Если
сложность
алгоритма
А
пропорциональна
функции
f(n) ,
а
сложность
алгоритма
В
пропорциональна
функции
g,
которая
растет
медленнее,
чем
функция
f,
то
совершенно
очевидно,
что
алгоритм
В
эффективнее
алгоритма
А,
если
размер
решаемой
задачи
достаточно
велик.
Сложность
алгоритма
является
решающим
фактором
при
оценке
его
эффективности.
Для
упрощения
анализа
алгоритмов
будем
использовать
некоторые
математические
свойства
обозначения
О-большое.
При
этом
следует
иметь
в
виду,
что
запись
ОИn))
означает
«порядка
f(n»>
или
«имеет
порядок
f(n»>.
Символ
О
-
это
не
функция.
1.При
оценке
сложности
алгоритма
можно
учитывать
только
старшую
степень.
Например,
если
алгоритм
имеет
сложность
О(n
3
+ 4*n
2
+ 3*n),
он
имеет
порядок
О(п
3
)
.
Из
таблицы,
показанной
на
рис.
3,
а,
видно,
что
слагаемое
п
3
намного
больше,
чем
слагаемые
4*n
2
и
3*n,
особенно при
больших
значениях
п,
когда
порядок
функции
n
3
+ 4*n
2
+ 3*
п
совпадает
с
порядком
функции
п
'.
Иначе
говоря,
эти
функции
имеют
одинаковый
порядок
роста.
Итак,
даже
если
сложность
алгоритма
равна
О(n
3
+ 4*n
2
+
3*n),
можно
говорить,
что
он
имеет
порядок
просто
О(n
3
)
.
Как
правило,
алгоритмы
имеют
сложность
О
(((n)) ,
где
функцией
f(n}
является
одна
из
функций,
перечисленных
на
рис.
3.
2.При
оценке
сложности
алгоритма
можно
игнорировать
множитель
при
старшей
степени.
Например,
если
алгоритм
имеет
11

Страницы