Оценка сложности алгоритмов

O(1) — константная сложность

Это время работы алгоритма, которое не зависит от входных данных. Например: простые арифметические операции, определение чётности целого числа (представленного в двоичном виде) и так далее.

O(n) — линейная сложность

Поиск наименьшего или наибольшего элемента в неотсортированном массиве, один проход по списку/массиву/словарю, зависит непосредственно от количества элементов.

O(log n) — логарифмическая сложность

Простейший пример — бинарный поиск. Если массив отсортирован, мы можем проверить, есть ли в нём какое-то конкретное значение, методом деления пополам. Проверим средний элемент, если он больше искомого, то отбросим вторую половину массива — там его точно нет. Если же меньше, то наоборот — отбросим начальную половину. И так будем продолжать делить пополам, в итоге проверим log n элементов. (Под понятием log n обычно имеется в виду логарифм n по основанию 2, однако обычно основание опускается).

O(n?) — квадратичная сложность

Такую сложность имеет, например, алгоритм сортировки вставками. В канонической реализации он представляет из себя два вложенных цикла: один, чтобы проходить по всему массиву, а второй, чтобы находить место очередному элементу в уже отсортированной части. Таким образом, количество операций будет зависеть от размера массива как n*n, т. е. n?. Грубо говоря, квадратичную сложность имеет цикл с вложенным циклом.

O(n?) — кубическая сложность

Такую сложность имеет обычное умножение двух n*n матриц. ОЧЕНЬ грубо говоря это цикл, в который вложен цикл, в который вложен цикл.

O(n!) — факториальная сложность

Обычно такую сложность имеют задачи, в которых реализуется полный перебор. Зачастую, такая сложность имеет место быть при небольших входных данных.

O(2^p(n)) — Экспоненциальная сложность

p(n) — полиномиальная функция от n. Пример: перемножение матриц с помощью полного перебора.

Это были основные типы сложности работы алгоритмов. Также существуют сложности, зависящие не от одного, а от нескольких независимых входных данных. Так мы можем получить сложность O(n*log n), если мы n раз проводим бинарный поиск или сложность O(n*m), если мы m раз проходим по массиву размером в n элементов. Также мы можем получить сложность O(n+m?), если, к примеру, мы пройдем по массиву один раз, проверив не отсортирован ли он, а затем отсортируем его с помощью алгоритма qsort.

Что за qsort?

Это quick sort, самый распространенный и простой алгоритм сортировки. Думаю, один из ближайших постов будет именно о нём.

Как мы видим, алгоритмов сортировки великое множество, и у всех из них есть как свои преимущества, так и недостатки. Также возможна реализация сортировки за линейное время на ядрах CUDA у Nvidia, но лишь при небольшом кол-ве элементов. Также, если вы всерьёз займетесь программированием, вы найдете для себя любимый способ сортировки(а, может, и вовсе напишите свой, как студенты МФТИ). К слову, у админа любимый способ сортировки — сортировка подсчетом(Counting Sort).

Существуют также сложности 2^n, 3^n и прочие, однако они не так распространены и малоэффективны. Постарайтесь не усложнять свой код до такой сложности по времени.

Попробуйте написать решение к этой задаче и оценить сложность алгоритма, зная приведенную выше информацию:

Вам известны два катета прямоугольного треугольника, найдите его гипотенузу и площадь. Используйте библиотеку math. Функция квадратного корня — math.sqrt()

Источник: m.vk.com

Комментарии: