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

UptoLike

ВУЗ: 

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

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

Рубрика: 

Если
время
решения
задачи
прямо
пропорционально
ее
размеру
п,
то
сложность
задачи
равна
О(n)
,
т.е.
имеет
порядок
n.
Если
время
решения
задачи
прямо
пропорционально
квадрату
ее
размера,
Т.е.
n
2
,
то
сложность
задачи
равна
о(n
2
)
и
т.д.
ОСНОВНЬIE
ПОНЯТИЯ
Определение
порядка
алгоритма
Алгоритм
А
имеет
порядок
Дн).
Этот
факт
обозначается
как
O(f(o)),
если
существуют
константы
k
и
по
такие,
что
при
решении
задачи,
имеющей
размер
n
?.nо,
алгоритм
А
выполняется
не
более
чем
за
k*f(n}
единиц
времени.
Условие
п
>
по
формализует
интуитивное
понятие
большой
задачи.
Как
правило,
этому
определению
удовлетворяет
большинство
значений
переменных
k
и
n.
Проиллюстрируем
определение
несколькими
примерами.
•
Допустим,
что
при
решении
задачи,
имеющей
размер
n,
алгоритм
выполняется
за
п
2
-3*п+
1
О
секунд.
Если
существуют
такие
константы
k
и
ПО,
что
k * n
2
> n
2
-
3*n+ 1
О
для
всех
п
~
по,
то
алгоритм
имеет
порядок
п
2
•
Фактически
если
константа
k
равна
3,
а
число
по
равно
2,
то
3 * n
2
> n
2
-
3 *n + 1
О
для
всех
п>
2,
как
показано
на
рис.2.
Таким
образом,
при
п
~
по
дЛЯ
выполнения
алгоритма
потребуется
не
более
k *
п:
')
единиц
времени.
•
Ранее
мы
показали,
что
для
вывода
на экран
первых
п
элементов
связанного
списка
потребуется
(n+ 1)
*(a+c)+n*w
единиц
времени.
Поскольку
неравенство
2*n
2:
n+ 1
выполняется
для
всех
n
2:
1,
имеет
место
неравенство
(2*а+2*с+
w)*n
2:
(n+
l)*(a+c)+n*
w
для
всех
п
2:
1.
Следовательно,
сложность
задачи
имеет
порядок
О(п).
Здесь
константа
k
равна
числу
2
*а+
2 *c+w,
а
константа
по
равна
1.
Требование
n
2:
по,
в
определении
величины
O(f(n))
означает,
что
оценка
времени
будет
корректной
лишь
для
достаточно
больших
задач.
Иными
словами,
если
задача
имеет
относительно
небольшие
размеры,
то
оценка
времени
ее
решения
будет
слишком
заниженной.
Например,
функция
log n
равна
О,
если
число
n
равно
1.
Итак,
из
того,
что
число
k * log 1
равно
О
при
любых
значениях
константы
k,
следует
неправильная
оценка
времени.
Для
выполнения
любого
алгоритма
требуется
не
нулевое
9

Страницы