Задание

Определения оценки сложности

квадратичная сложность

Логарифмическая сложность

Линейная сложность

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

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

пример- алгоритм поиска наибольшего элемента в не отсортированном массиве. Надо пройтись по всем n элементам массива, чтобы найти максимальный.