19. Что такое Big O? Как происходит оценка асимптотической сложности алгоритмов?

Big O (O большое / символ Ландау) - математическое обозначение порядка функции для сравнения асимптотического поведения функций.

Асимптотика - характер изменения функции при стремлении ее аргумента к определённой точке.

Любой алгоритм состоит из неделимых операций процессора(шагов), поэтому нужно измерять время в операциях процессора, вместо секунд.

DTIME - количество шагов(операций процессора), необходимых, чтобы алгоритм завершился. Временная сложность обычно оценивается путём подсчёта числа элементарных операций, осуществляемых алгоритмом. Время исполнения одной такой операции при этом берётся константой, то есть асимптотически оценивается как O(1).

Сложность алгоритма состоит из двух факторов: временная сложность и сложность по памяти.

Временная сложность - функция, представляющая зависимость количество операций процессора, необходимых, чтобы алгоритм звершился, от размера входных данных.

Все неделимые операции языка(операции сравнения, арифметические, логические, инициализации и возврата) считаются выполняемыми за 1 операцию процесора, эта погрешность считается приемлемой.

При росте N, слагаемые с меньшей скорость роста всё меньше влияют на значение функции. Поэтому, вне зависимости от констант при слагаемых, слагаемое с большей скорость роста определяет значение функии. Данное слагаемое называют порядком функции. Пример: Т(N) = 5 * N^2 + 999 * N... Где (5 * N^2) и (9999 * N) являются слагаемыми функции.

Константы(5 и 999) не указываются в рамках нотации Big O, так как не показывают абсолютную сложность алгоритма, так как могут изменяться в зависимости от машины, поэтому сложность равна О(N^2).

В порядке возрастания сложности:

1. O(1) - константная, чтение по индексу из массива
2. O(log(n)) - логарифмическая, бинарный поиск в отсортированном массиве
3. O(√n) - сублинейная
4. O(n) - линейная, перебор массива в цикле, два цикла подряд, линейный поиск наименьшего или наибольшего элемента в неотсортированном массиве
5. O(n*log(n)) - квазилинейная, сортировка слиянием, сортировка кучей
6. O(n^2) - полиномиальная(квадратичная), вложенный цикл, перебор двумерного массива, сортировка пузырьком, сортировка вставками
7. O(2^n) - экспоненциальная, алгоритмы разложения на множители целых чисел
8. O(n!) - факториальная, решение задачи коммивояжёра полным перебором

Алгоритм считается приемлемым, если сложность не превышает O(n*log(n)), иначе говнокод.

Предыдущий вопрос: 18. Какие паттерны используются в Hibernate?

Следующий вопрос: 20. Что такое рекурсия? Сравните преимущества и недостатки итеративных и рекурсивных алгоритмов. С примерами.

Все вопросы по теме: список

Все темы: список

Вопросы/замечания/предложения/нашли ошибку: напишите мне