lection19.10
.pdf
Вступление Время O-нотация Функции Память Алгоритмы Инструменты Философия Источники
Примеры
Поиск минимального элемента в массиве.
O(N)
Поиск максимального элемента в массиве.
O(N)
Поиск минимального элемента в отсортированном массиве. O(1)
Поиск элемента с заданным значением в отсортированном массиве. O(log N)
Проверка числа на простоту.
Сложность алгоритмов |
В.А. Дель, студент гр. 529-1 |
11 / 31 |
Вступление Время O-нотация Функции Память Алгоритмы Инструменты Философия Источники
Примеры
Поиск минимального элемента в массиве.
O(N)
Поиск максимального элемента в массиве.
O(N)
Поиск минимального элемента в отсортированном массиве. O(1)
Поиск элемента с заданным значением в
отсортированном массиве. O(log N) p
Проверка числа на простоту. O( N)
Сложность алгоритмов |
В.А. Дель, студент гр. 529-1 |
11 / 31 |
Вступление Время O-нотация Функции Память Алгоритмы Инструменты Философия Источники
Примеры
|
Поиск минимального элемента в массиве. |
||
|
O(N) |
||
|
Поиск максимального элемента в массиве. |
||
|
O(N) |
||
|
Поиск минимального элемента в |
||
|
отсортированном массиве. O(1) |
||
|
Поиск элемента с заданным значением в |
||
|
отсортированном массиве. O(log N) |
||
|
p |
|
|
Проверка числа на простоту. O( N) |
|||
|
Нахождение НОД двух чисел. |
||
Сложность алгоритмов |
В.А. Дель, студент гр. 529-1 |
11 / 31 |
Вступление Время O-нотация Функции Память Алгоритмы Инструменты Философия Источники
Примеры
Поиск минимального элемента в массиве.
O(N)
Поиск максимального элемента в массиве.
O(N)
Поиск минимального элемента в отсортированном массиве. O(1)
Поиск элемента с заданным значением в
отсортированном массиве. O(log N) p
Проверка числа на простоту. O( N)Нахождение НОД двух чисел. O(log N)
Сложность алгоритмов |
В.А. Дель, студент гр. 529-1 |
11 / 31 |
Вступление Время O-нотация Функции Память Алгоритмы Инструменты Философия Источники
Порядок роста функций
O(1)
O(log N) p
O( N)
O(N)
O(N log N)
O(N2)
O(N3)
O(2N )
O(N!)
Сложность алгоритмов |
В.А. Дель, студент гр. 529-1 |
12 / 31 |
Вступление Время O-нотация Функции Память Алгоритмы Инструменты Философия Источники
Порядок роста функций
Сложность алгоритмов |
В.А. Дель, студент гр. 529-1 |
13 / 31 |
Вступление Время O-нотация Функции Память Алгоритмы Инструменты Философия Источники
Емкостная сложность
Емкостная сложность характеризует количество используемой памяти для решения задачи.
Для примера рассмотрим различные сортировки.
Сложность алгоритмов |
В.А. Дель, студент гр. 529-1 |
14 / 31 |
Вступление Время O-нотация Функции Память Алгоритмы Инструменты Философия Источники
Сортировки
Сложность алгоритмов |
В.А. Дель, студент гр. 529-1 |
15 / 31 |
Вступление Время O-нотация Функции Память Алгоритмы Инструменты Философия Источники
Сортировки
Пузырьковая сортировка. Время: O(N2), память: O(1).
Сложность алгоритмов |
В.А. Дель, студент гр. 529-1 |
15 / 31 |
Вступление Время O-нотация Функции Память Алгоритмы Инструменты Философия Источники
Сортировки
Пузырьковая сортировка. Время: O(N2), память: O(1).
Сортировка вставками. Время: O(N2), память: O(1).
Сложность алгоритмов |
В.А. Дель, студент гр. 529-1 |
15 / 31 |