Сложность алгоритма Большое О
Вставка
- Опубліковано 6 жов 2024
- Хотите повлиять на темы сюжетов? Вам сюда
itspher...
Я в ВК id26420520
Группа в ВК itspher...
Опрос в группе itspher...
Всем привет как и обещал отснял сюжет посвященный определению временной сложности выполнения алгоритмов. На собеседовании об этом обычно не спрашивают но могут спросить в контексте какой-нибудь другой темы. Например задать такой вопрос “Напишите временную сложность поиска в 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 от количества страниц в справочнике.
Отличная работа! Спасибо, друг!
неплохая попытка! но скажу честно, если бы я раньше этот вопрос не изучал, то только просмотрев это видео вряд ли что-нибудь бы понял )) говорю ж не хватает визуализации... например хотя бы что-нибудь в таком стиле cs.usfca.edu/~galles/visualization/Algorithms.html
да видел примеры в динамике картинка на первом шаге, потом на втором, потом на третьем... но без анимации не оно (( за то что тратишь силы и пытаешься делать хоть как умешь, ставлю лайк ))
Спасибо за ссылку, я ее изучу! Визуализация нужна! Вообще стараюсь от выпуска к выпуску наращивать качество. А новые подписчики и лайки придают заряд положительных эмоций)))
***** Только что посмотрел ссылку. Офигенно!!
Будников Александр теперь нужно каким-то чудом скрестить твои обяъяснения с этой офигенной анимацией ))
Sergii Dotsenko, благодарю за отличную ссылку. Это чудесно!
Автору спасибо, что взялся за эту тему, но скорость изложения превосходит все разумные пределы переваривания информации! Надо по десять раз перематывать назад чуть ли не каждое предложение, чтобы понять главную мысль! Помедленнее, пожалуйста! Я записываю :)
А я чота сразу понял
Норм, особенно когда привык смотреть x2
а мне понравилось, так держать
Красавчик)
На 1:16.
f(n) = O(g(n))
"функция f растет медленнее, чем g", следующий кадр "при c = c1 и n = N"
Я не понял, откуда взялось c?
Не обращайте внимания. Просто смотрите дальше, и без начала всё становится понятно.
Класть, а не лОжить)))
Спасибо, большое! Супер!
Все ясно и понятно!!!!
Не, ну земля и небо! Вообще круто смотрится! Соглашусь с@СергійДоценко, не возможно все понять только просмотрев видео, а еще КЛАСТЬ, а не "ложить". Ну а так супер, даже не верится что это ты!
вот здесь вот )))))))))))))))
Спасибо за информацию
Спасибо огромное, очень круто, хорошо объясняешь!
Это понятно когда уже сам все знаешь, а если тебе надо понять то даже и не слушай
Для бинарного дерева O(log n) будет в лучшем случае, и O(n) в худшем, если оно не сбалансировано (входные данные были отсортированными)
Да ладно вам. Смотрю на скорости ускоренно полтора и все очень разжевано и понятно! Повторить тему самое оно.
Так я и не понял, Серёга нашел номер Светки?
Вы можете сделать примеры оценки сложности с небольшими источниками на С++?
Когда страницы перепутаны, а Сереге нужно найти номер Светки - ему мало просто все страницы просмотреть? Нафиг он их сортирует)))? Это ж 2 разные задачи, причем не связанные по большому счету. Пример - отстой)
не хватает визуализации, или мнемоники. При просмотре видео не задействуется зрительная память. Это ухудшает запоминание)
Oh yeah, спасибо, m8 )0))
Бедный Серёга
было бы удобнее информацию воспринимать графически,
т.е. в виде
функция
название
график
и только потом объяснение. На слух воспринимается тяжеловато (
Kupil dom za 250 000 Euro, kupil noviy zamok dlya novogo doma za 4,99 Euro. Za skolko oboshlos mne dom? Mi govorim za 250 000 Euro a ne 250 004,99 Euro. 250 000 Euro eto i est bolshoe O!!
Не понятно, что за "c" и "c1" в формуле f(n) = O(g(n))? И скажем если с1 = 0.1*e-1000 и n = 3, то будет ли всегда c1*g(3) >= f(3)? В общем вообще не понятно что такое "с" и как его выбирать.
Ложит.....Автору тоже нужен справочник, только уже не с телефоном Светки )). Автор, ты не рэпчик читаешь, помедленнее, пожалуйста!
ложит!!!
слишком громкая музыка в конце (слушал в наушниках), в остальном спасибо, полезно было
Без бороды однозначно лучше)) По сути, не могу понять не проще ли сделать чтот типа презентации с голосовым сопровождением. Картинка дергается, ты перескакиваешь с места на место - немного корявенько. и самое главное - медленнее излагай.
03:52 на каком уровне то
Ты сам то понял что протараторил? Или ты просто откуда то считал? Ты объясняешь тем кто НЕ понимает а не тем кто понимает. Вспоминай об этом иногда, чувак
Не понимал, не изучал, это и не требуется. Нужно просто знать математику 10-11й класс + сами алгоритмы. Теперь стало понятно.
+
*исходниками*
Определения О не верные
Игорь Клейнер Добрый день. Спасибо. за замечание. Если не затруднит не могли бы в комментарий написать где я ошибаюсь. Я вставлю аннотацию с текстом.
не дан ответ про хешмап, и даже в коментарии не соизволил написать. диз
Верни бороду!!!
Невнятная дикция