lection19.10
.pdf
Вступление Время O-нотация Функции Память Алгоритмы Инструменты Философия Источники
Оценка сложности
Перебираем все возможные значения x.
Для каждого x перебираем все возможные значения y.
Для каждой пары (x; y) считаем значение функции.
Ответ: O(CNM) = O(NM).
Сложность алгоритмов |
В.А. Дель, студент гр. 529-1 |
10 / 31 |
Вступление Время O-нотация Функции Память Алгоритмы Инструменты Философия Источники
Оценка сложности
Перебираем все возможные значения x.
Для каждого x перебираем все возможные значения y.
Для каждой пары (x; y) считаем значение функции.
Ответ: O(CNM) = O(NM). Верхняя оценка: 108 операций.
Сложность алгоритмов |
В.А. Дель, студент гр. 529-1 |
10 / 31 |
Вступление Время O-нотация Функции Память Алгоритмы Инструменты Философия Источники
Примеры
Поиск минимального элемента в массиве.
Сложность алгоритмов |
В.А. Дель, студент гр. 529-1 |
11 / 31 |
Вступление Время O-нотация Функции Память Алгоритмы Инструменты Философия Источники
Примеры
Поиск минимального элемента в массиве.
O(N)
Сложность алгоритмов |
В.А. Дель, студент гр. 529-1 |
11 / 31 |
Вступление Время O-нотация Функции Память Алгоритмы Инструменты Философия Источники
Примеры
Поиск минимального элемента в массиве.
O(N)
Поиск максимального элемента в массиве.
Сложность алгоритмов |
В.А. Дель, студент гр. 529-1 |
11 / 31 |
Вступление Время O-нотация Функции Память Алгоритмы Инструменты Философия Источники
Примеры
Поиск минимального элемента в массиве.
O(N)
Поиск максимального элемента в массиве.
O(N)
Сложность алгоритмов |
В.А. Дель, студент гр. 529-1 |
11 / 31 |
Вступление Время O-нотация Функции Память Алгоритмы Инструменты Философия Источники
Примеры
Поиск минимального элемента в массиве.
O(N)
Поиск максимального элемента в массиве.
O(N)
Поиск минимального элемента в отсортированном массиве.
Сложность алгоритмов |
В.А. Дель, студент гр. 529-1 |
11 / 31 |
Вступление Время O-нотация Функции Память Алгоритмы Инструменты Философия Источники
Примеры
Поиск минимального элемента в массиве.
O(N)
Поиск максимального элемента в массиве.
O(N)
Поиск минимального элемента в отсортированном массиве. O(1)
Сложность алгоритмов |
В.А. Дель, студент гр. 529-1 |
11 / 31 |
Вступление Время O-нотация Функции Память Алгоритмы Инструменты Философия Источники
Примеры
Поиск минимального элемента в массиве.
O(N)
Поиск максимального элемента в массиве.
O(N)
Поиск минимального элемента в отсортированном массиве. O(1)
Поиск элемента с заданным значением в отсортированном массиве.
Сложность алгоритмов |
В.А. Дель, студент гр. 529-1 |
11 / 31 |
Вступление Время O-нотация Функции Память Алгоритмы Инструменты Философия Источники
Примеры
Поиск минимального элемента в массиве.
O(N)
Поиск максимального элемента в массиве.
O(N)
Поиск минимального элемента в отсортированном массиве. O(1)
Поиск элемента с заданным значением в отсортированном массиве. O(log N)
Сложность алгоритмов |
В.А. Дель, студент гр. 529-1 |
11 / 31 |