Как оценить временную сложность алгоритма?
Задача: Дан целочисленный массив. Необходимо найти два наиболее часто встречающихся элемента массива. Временная сложность вашего алгоритма должна быть не выше O(n log n), где n — размер массива.
Есть два варианта решения:
Отсортировать массив, после чего найти искомые элементы за один проход.
За один проход массива заполнить HashMap, где ключ - уникальный элемент массива, а значение - его количество в массиве. Найти искомые элементы в HashMap.
Временные оценки сложности:
O(1) < O(log n) < O(n). < O(n log n) < O(n^2) < O(n^3) < O(n!)
Сортировка Quick Sort дает в среднем O(n log n), а в худшем случае O(n^2).
Merge Sort дает в худшем случае O(n log n).
Поиск и вставка в HashMap в худшем случае дают O(n).
Однократный проход массива это скорее всего O(n).
Таким образом в первом случае получаем: сортировка O(n log n) + обработка массива O(n).
Во втором случае: обработка массива, поиск, вставка, поиск итогового результата - все четыре операции по O(n).
Собственно вопросы:
Вариант с Merge Sort будет удовлетворять ограничению O(n log n) или выйдет за него за счет O(n log n) + O(n)? Сложность второго алгоритма будет O(n) или все же больше? Как правильно проводится оценка итоговой временной сложности алгоритмов?
Ответы (1 шт):
Вариант с Merge Sort будет удовлетворять ограничению O(n log n) или выйдет за него за счет O(n log n) + O(n)?
Есть утверждение: если f = O(g), то O(f + g) = O(g). То есть, к более "сложной" функции можно прибавлять сколько угодно не таких "сложных" функций, результат не поменяется.
Добавка линейного прохода по массиву к сортировке общую сложность алгоритма не меняет. Будет O(n log n).
Сложность второго алгоритма будет O(n) или все же больше?
Операции с хэш-таблицой имеют среднюю сложность O(1) и равномерную/худшую сложность O(n). Следовательно и окончательный алгоритм с использованием хэша будет иметь
O(n) – сложность в среднем,
O(n2) – равномерная сложность.
На практике это значит что работать будет быстро, но если захочется, можно составить такой пример входных данных что будет очень медленно.
Как правильно проводится оценка итоговой временной сложности алгоритмов?
Найдите Кормена-Лэйзерсона, почитайте первые главы, там довольно кратко делается введение в тему.
Или вот программа:
- Учите эпсилон/дельта определения, немного пределов.
- Учите элементарные функции из анализа и как у них соотносятся скорости роста.
- Учите O-большое, o-малое, Ω, Θ. Доказываете множество теорем на подобие теоремы про сумму функций вверху.
- Учите сложности элементарных операций в языке программирования и его стандартной библиотеке.
- Учите как комбинируются сложности в конструкцияx языка программирования (вложенные циклы, последовательные операции и т.п.).
- Учите метод математической индукции для рекурсивных алгоритмов.
- Учите производящие функции для действительно сложных случаев.
- Готово.
Шучу, шучу! Но тема и правда обширная.