Сложность алгоритма Большое О

Хотите повлиять на темы сюжетов? Вам сюда
https://vk.com/itspherechannel?w=wall-68704273_8%2Fall
Я в ВК https://vk.com/id26420520
Группа в ВК https://vk.com/itspherechannel
Опрос в группе https://vk.com/itspherechannel?w=wall-68704273_3%2Fall

Всем привет как и обещал отснял сюжет посвященный определению временной сложности выполнения алгоритмов. На собеседовании об этом обычно не спрашивают но могут спросить в контексте какой-нибудь другой темы. Например задать такой вопрос “Напишите временную сложность поиска в ArrayList”. Поэтому данный ролик надеюсь будет полезен и подготовит вас к подобного рода вопросам. Про ArrayList и LinkedList можно посмотреть тут а про HashMap тут. Кстати количество аннотаций походу будет расти линейно в зависимости от количества роликов на моем канале)). Не, не будет!)

Я думаю что большинство из вас уже не раз встречали с таково рода обозначениями

f(n) = O(1) константа
f(n) = O(log(n)) логарифмический рост
f(n) = O(n) линейный рост
f(n) = O(n*log(n)) квазилинейный рост
f(n) = O(n^m) полиномиальный рост
f(n) = O(2^n) экспоненциальный рост

Мне кажется не разумным способ просто запоминать какому алгоритму относится тот или иной класс сложности. Гораздо полезнее уметь в уме примерно прикинуть насколько изменится время выполнения при увеличении входных данных(N). Тогда я постараюсь рассказать как это можно сделать.

O(1) - Начнем пожалуй с константной сложности.

Представим что студент Серега в своем тел. справочнике загнул страничку с телефоном его одногруппницы Светки. Это позволяет искать номер Светки в среднем за константное время т. к. нет прямой зависимости от количества номеров или она очень невелика на столько что ей можно пренебречь.

Почему в среднем? Да потому что ему приходилось перебрать определенное количество записей на данной страничке этим числом можно пренебречь также т. к. оно мало.
Примером может служить поиск в хеш-таблице если в одной “корзинке” один объект.

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

С логарифмической сложность уже посложнее. Представим что Серега только познакомился со Светкой. Он знает ее фамилию как он будет искать страничку с ее номером? Он открыл справочник в середине и попал на какую-то запись смотрит а там фамилия начинается на букву которая в алфавите идет раньше чем фамилия Светки. Значит Светка находится во второй половине справочника. Теперь он берет стопку листов справочника где предположительно находится его Светка. И открывает эту стопку тоже по середине и так далее пока не найдет Светку. Понимаете? Получается такой бинарный поиск. Количество сравнений которые ему потребуется сделать будет равняться log по основанию 2 от количества страниц в справочнике.

Видео Сложность алгоритма Большое О канала Будников Александр