Оценка сложности алгоритма. Сложность алгоритмов. Big O, Большое О

[@AlexeyShram]

На 13:50 говорится: "На самом деле степенная функция растет гораздо быстрее N в степени 100. Таким образом ответ будет O(2^n)" Допущена ошибка, т.к N^100 - это и есть степенная функция.

[@Cronis]

Спасибо! Оговорился :)

[@TheANTIdos]

Правильнее было бы сказать, что можно доказать, что показательная функция на бесконечности растет быстрее степенной, вот и все. А так - да, большое спасибо за видео!

[@yarikleto5515]

@@ic6406 да, действительно n^100 растет быстрее (когда n - небольшое число), чем 2^n. А так они очень похожи

[@vanjka39]

@@ic6406 если рассмотреть функцию f(x)=2^x/x^10, видно что при x~100 f(x)>1, соответственно, показательная функция растет быстрее при x->inf

[@jonyxip]

@@ic6406 любая экспоненциальная функция растет быстрее чем полином.

[@afriendRU]

Просто бомба! Долго боялся взяться разузнать что такое сложность алгоритмов. Тут всё лаконично и объясняется до самого основания. Большое спасибо)

[@ВолодимирБарибін-е8у]

Спасибо, благодаря вашему видео у меня сложилось хоть какое-то понятие о "Big O".

[@lobaevni]

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

[@Cronis]

Никита Лобаев, спасибо! Был рад помочь!

[@pewpew7937]

Дело говорит, твое видео самое полезное на эту тему во всем интернете. Большое спасибо за твой труд)

[@Ana-rv6xm]

Это материал по книге для подготовки к интервью CRACKING CODING INTERVIEW 189 PROGRAMMING Questions & SOLUTIONS

[@Cronis]

Читайте описание видео)

[@ua_dimka]

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

[@Alexander-is1eq]

Полезная информация начинается где то с 6 минуты. Хотел уж было бросить смотреть, но слава богу не бросил. Полезная информация на самом деле полезная. Очень хорошо и понятно все объяснено, спасибо большое.

[@Cronis]

Рад, что досмотрели :)

[@michaeltes8864]

Очень понятно и доступно, все разложено по полочкам. Хотя и понятно, что это лишь вершина айсберга. Огромное спасибо автору!!!

[@fusome]

спасибо, человеческим языком и доходчиво. Наконец-то кто-то это сделал

[@xelaksal6690]

Огромное спасибо, всё ПРЕДЕЛЬНО понятно!

[@Cronis]

Спасибо! :)

[@sergeyspitsyn3220]

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

[@Cronis]

Сергей, вы абсолютно правы. К сожалению сделали ошибку при записи :(

[@goranlukash1374]

Реально спасибо за понятное объяснение....😁

[@gofracarton]

Спасибо вам! Проходил курсы от Яндекса по алгоритмам, где объясняли big O, но ничего не понял, а вы очень доходчиво и подробно объяснили. Ещё раз спасибо!

[@Cronis]

Рад помочь!

[@vladimirteplov8060]

Отличное видео и курс! Спасибо!

[@Cronis]

Рад помочь!

[@МатвейПодгорный-р4к]

Отличный и подробный разбор, качественное объяснение материала, спасибо большое

Спасибо огромное за видео ! Все так понятно, особенно на конкретных примерах 💙

[@Cronis]

Спасибо за комментарий!

[@ebymamky]

Просто супер, спасибо!!! Отдельное спасибо за примеры

[@Cronis]

Всегда рад помочь!

[@Devivl]

Спасибо. В общих чертах стало понятно.

[@olegchumin6634]

Лучшее объяснение, что видел вообще.

[@vvlkblkc]

Очень хорошее разъяснение - лучшее, что я видел.

[@Cronis]

Рад помочь!

[@awakeupcall5336]

22:58 подскажите, откуда с неба взяли L * log L ?

[@Cronis]

В видео говорится, что мы сортируем строки длиной L. В любой сортировке есть всегда код вида if(str1 > str2). А сравнение строк одинаковой длины L -- это сравнение их L символов. Следовательно, мы умножаем сложность сортировки на L

[@bahakulbarakov494]

Сложно очень воспринимать с первого раза XD. С 4 раза понял что да как. Объясняете очень хорошо спасибо за видео.

[@АлексСапс]

Спасибо! отличные примеры из жизни. Очень наглядно! на 13:57 нагляднее пожалуй сравнивать 2^N and N^2. И первый график будет расти быстрее, намного быстрее второго, поэтому второй можно отбросить.

[@Alex-zn6vj]

Благодарю! Желаю вам всего самого наилучшего просто вау! ВСЕ ПОНЯТНООО!!!))

[@yeson6581]

7:06, при передаче на самолёте размер передаваемых файлов не увеличивается, то есть по оси "Количество бит" нет изменения, меняется только время полёта, в зависимости от погодных условий и скорости самолёта. Прямая должна быть вертикальной. Тогда это конечно будет менее наглядно, но оси можно поменять местами и всё будет ok.

[@Cronis]

При росте количеств бит время не меняется. График верный

[@kirillsushilnikov9614]

Спасибо, было познавательно

[@ifdru74]

Большое спасибо за видео. Лично для меня тема стала понятнее.

[@Cronis]

Приходите к нам на интенсив, узнаёте ещё больше: kzbin.info/www/bejne/fJm2ZnybeLFrhbc

[@ЕвгенЗадко]

Очень полезное видео для старта в изучении сложности алгоритмов!

[@ИльяИлья-ф8щ]

Спасибо за такие простые обьяснения, подписка!

[@Гарри-ю3и]

Круто, очень живо и ясно. Огромное спасибо!

[@cracoh]

Спасибо зо подробное и доходчивое объяснение ключевых базовых понятий. 25 минут видео я посмотрел за час - прорешивал, записывал. Не знаю было ли где-то в комментах, но меня покоробила фраза на 17.11 - "сколько раз нужно умножить 1 на 2 чтобы получить 16?" мой ответ 8. потому как 1*2+1*2+1*2+1*2=8 а не 4. Но, в общем понятно что имелось в виду.

[@Roomaa111]

1*2*2*2*2=16

[@cracoh]

@@Roomaa111 хех, класс!

[@andrusia2048]

@@Roomaa111 на сколько двоек нужно умножить единицу

[@ЕвгенийСедых-и2щ]

Спасибо, все лаконично, кратко и понятно!

[@ОлафШкипер]

Я не очень сведущ в языках но на 19:11 в цикле скобки разные стоят[) потому сложность будет 0. Видос конечно супер щикарный, с примерами, по делу, без тормозов. Респект!

[@Математик-л7ы]

А почему на 24:12 сложность сортировки строки log(l) ?

[@Cronis]

Сложность написана L * log (L)

[@andrewstrelnikov8700]

16:59 Сколько раз нужно умножить 1 на 2 чтобы получить 16? В целом ход лекции мне нравится. Но вот бы поправили несколько ошибок...

[@Cronis]

1*2*2*2*2 = 16 сколько раз вы умножили 1 на 2 чтобы получить 16?

[@shurale85]

Скажите, пожалуйста, а почему сортировка строки L*Log_L?

[@Cronis]

Встроеннная в язык сортировка это сонтировка quicksort. Ей мы и сортируем строки. И ее сложность O(L * logL)

[@pinkierar_real]

@@Cronis это бы совершенно неочевидно)

[@zion4d]

пожалуй лучшее! теперь можно приступать к "грокаем алгоритмы"

[@Cronis]

Спасибо! Грокаем алгоритмы -плохая, поверхностная книга, которая путает больше, чем помогает.

[@zion4d]

@@Cronis спасибо! Учту!

[@superninja2749]

Здравствуйте, почему 16:20 говорится, что мы должны искать число сначала в 16 элементах, если мы уже делим его на два? то есть, мы ищем в 8 элементах, немного не понял момент.

[@Cronis]

Сначала в массиве 16 элементов, потом 8, потом 4, потом 2, потом 1. Поэтому мы сначала ищем среди 16 элементов

[@PapaCarlo87]

Спасибо ,очень информативно и доступно!

[@bor3007]

Бро ты крут! Лайк однозначно. Пошел дальше готовиться к собеседованию в фейсбук

[@dmitry4638]

Отличное разъяснение, спасибо!

[@MrCoolDolphin]

Офигенное видео!!! Большое спасибо автору!

[@dimaspng]

Спасибо от души!

[@Cronis]

На здоровье)

[@Noir_Egoiste]

Больше спасибо, но ничего не понятно, log N получается в половину меньше чем N и в меньше чем N^2 ?

[@jakepomg317]

Не понятно в 7 примере 24:15. O(N * L * log L + L * N * log N), так почему же появились скобки для логарифмов?: O(N * L * (log N + log L)) Ведь если взять пример: 2 * 2 + 2 будет равно 6, поставив скобки: 2 * (2 + 2) ответ уже будет 8 Только начал вариться в этой теме, может тут как-то по другому работает

[@Cronis]

Просто вынесли за скобки N * L. То есть не вашем примере 2 + 2 * 2 = 2 * (1 + 1 * 2)

[@jakepomg317]

@@Cronis Спасибо🙏 3 года прошло, а ответ за сутки, респект)

[@maksimsergeevich5939]

Подскажите пожалуйста, если формула расчета кол-ва итераций для алгоритма сортировки равна - n*(n/10) то какая здесь сложность получается? O(n) или O(n^2) ? Должен ли я отбросить n/10 так как это "n" становится в 10 раз меньше другого n. Или правильней будет отбросить знаменатель 10, тогда получится, что у нас остается n^2. Как правильно? Я не понимаю... Если ответите, сразу поясните пожалуйста, почему должен быть именно такой ответ. Или в видео неточность? Может правильное сказать, что незначительное n это не то которое более чем в 2 раза больше, а то которое меньше на степень другого n?

[@Cronis]

Добрый день! Здесь сложность N^2 т.к. мы отбрасываем константы все, а 10 это констатнта. Правило очень простое -- все что константа сразу отбрасывается, а из оставшихся слагаемых выбирается то, у которого выше скорость роста (еще называют порядок). Градация по убыванию: N! -> 2^N -> N^2 -> N * log N -> N -> SQRT(N) -> log N -> 1

[@maksimsergeevich5939]

@@Cronis Спасибо! Все понятно теперь! А там где N^2 подразумевается число в любой степени? от 2 и выше? Если будет N^2 * N это будет N^3?

[@Cronis]

@@maksimsergeevich5939 Не за что :) N^2 < N^3 < N^... < N^X чем меньше степень, тем меньше скорость роста т.е. N^2 + N^3 = O(N^3)

[@TarasMaliarchuk-o4d]

12:43 n< n^2 , n -> inf не тому, що в 2 рази більша друга функція (вона взагалі в n раз більша) , а тому , що похідна другої функції рівна 2n , а першої 1, отже inf > 1, тому і нехтуємо.

[@turbojonah2881]

Здравствуйте, спасибо за видео! Есть один вопрос. На 20:05 вы говорите, что сложность алгоритма будет ровна О(N+(N-1)+(N-2)+...+2+1). Не совсем понятно почему вы складываете кол-во операций, ведь в предыдущем примере с вложенным циклом, сложность алгоритма ровнялась О(N*N). Разве тут не должно было получится, что сложность алгоритма ровняется О(N*N+N(N-1)+N(N-2)+...+2N+N?

[@Cronis]

Добрый день! Смотрите: в первом цикле i = 0, то есть второй цикл идёт от j = 0 до N. Затем i = 1 то есть второй цикл идёт от j = 1 до N затем второй цикл идёт от j = 2 до N. Следуя этой логике, получаем N+(N-1)+(N-2)+...+2+1

[@павелшимаров-ц3о]

@@Cronis Не согласен. На первой итерации выполняем вложенный цикл N раз по N раз, у этой итерации О(N*N); затем N раз по N-1 раз, О(N*(N-1));затем N раз по N-2 раз, О(N*(N-2)) и т.д. Так как итерации выполняются последовательно, то О итераций складываем: О(N*N+N(N-1)+N(N-2)+...+2N+N), после упрощения ответ будет такой же как в видео О(N*N), но описание как его получили в видео не правильное.

[@MrPr0927]

@@Cronis тут вы не правы, из N+(N-1)+(N-2)+...+2+1 никак не вывести N^2, следовательно, как и писали выше правильная запись будет вида N*(N+(N-1)+(N-2)+...+2+1)

[@Cronis]

@@MrPr0927 это арифметическая прогрессия. Можете подробнее прочитать здесь: ru.wikihow.com/%D1%81%D0%BB%D0%BE%D0%B6%D0%B8%D1%82%D1%8C-%D1%86%D0%B5%D0%BB%D1%8B%D0%B5-%D1%87%D0%B8%D1%81%D0%BB%D0%B0-%D0%BE%D1%82-1-%D0%B4%D0%BE-N

[@MrPr0927]

@@Cronis Ок, понял, тоесть не во всех случаях когда видим вложенный цикл нужно подразумевать перемножение сложностей, как было сказано ранее в видео?

[@88billizzard88]

Супер круто, спасибо огромное, очень понятно и информативно, просто бомба

[@Cronis]

Спасибо за добрые слова!

[@iforand]

7:28 Как это O(0) означает, что ничего не происходит? O(0) означает, или что для выполнения задачи не требуется выполнять каких либо действий, или что количество операций для выполнения задания уменьшается с ростом сложности задачи асимптотически к нулю. Раньше же сказано, что оценка верхней границы не зависит от времени, а значит говорить, что-то что-то происходит или не происходит не корректно.

[@Cronis]

Вы полностью правы. Но как это все сказать для простого человека, который впервые это видит и не напугать его сложными формулировками? :) поэтому вот просто и сказано - суть отражает и не пугает. Под видео есть ссылка на оценку сложности со строгой математикой и с теорией множеств на 2.5 часа. Там мы рассказываем уже все четко для тех, кому нужна математическая строгость. А здесь для широкого зрителя :)

[@ФдрФфф]

6:34 что такое "О" и "(n)".

[@vonarut]

Огромное Спасибо! Наконец-то понял что такое big O !!! 2019 !!!

[@nexissis51]

Очень хорошее и познавательное видео

[@Cronis]

Спасибо!

[@Евгений-ы4м3ж]

А про бинарный поиск не проще корень квадратный от N ?

[@ruslanvolovik2745]

На самом деле log2N это будет когда мы будем точно делить список(массив) попалам на каждой итерации но мы можем же делить на 3, 4 и тд частей и уже не получится логарифм с основанием 2 поэтому в видео есть неточности. Основа логарифма отбрасывается не из-за того что это константа а из-за того что деление списка может быть больше чем на 2 части

[@Cronis]

Спасибо за комментарий! Основание логарифма это константа. Доказательство это свойство 13: 2.bp.blogspot.com/-RFm5xlyqFf0/WuBL2YudoEI/AAAAAAAAByk/tRjvR5l7FvkB_ylwBEPEh_8x63UTxW8kwCLcBGAs/s1600/009.jpg По поводу как он образуется: именно деление объекта пополам дает основание 2. Если бы вы делил на части 25% и 75%, было бы основание 4/3. Что тоже константа

[@ruslanvolovik2745]

@@Cronis ок

[@manOfPlanetEarth]

@@ruslanvolovik2745 а как с гонором ты начал. и тут де в лужу сел. неуч😂

[@ruslanvolovik2745]

@@manOfPlanetEarth неуч то ты, я смотрел этот весь бред по сложность алгоритмов и подобную пургу только ради интереса, не более. Я понял, что все это бесполезные вещи, потому что у меня есть друг с которым каждый день общаюсь, он недавно закончил стажировку в гугле, сам сказал что пободные хрени не пригодились в самом гугле, что его очень сильно удивило. Учи дальше этот бред никому не нужный (деньги оно тебе не принесет, баран)😱

[@manOfPlanetEarth]

@@ruslanvolovik2745 ты в москве сейчас?

[@C2H5OHH]

Спасибо за урок!

[@alexzhyshko9762]

В примере 3 было сказано, что сложность алгоритма N^2, но если посмотреть внимательнее, то N(N-1)(N-2)...1 это Nфакториал. Тоесть будет О(N!). И если смотреть по квадрату 4х4,то отсекается не половина, а немного меньше половины, что, логично предположить, будет О(nlogn). И если расписывать эти два случая, то мы получим равенство сложностей N! =~ NLogN. Если в чем-то не прав, то поправьте пожалуйста

[@Cronis]

будет: N + (N - 1) + (N - 2) .... + 3 + 2 + 1 = N(N+1)/2 = O(N^2) В треугольнике тоже кружки идут как 4 + 3 + 2 + 1 = 4*(4+1)/2 = 10

[@awakeupcall5336]

17:17 смущает запись "сколько раз умножить 1 на 2 чтобы получить 16?" сколько раз не умножай 1 на 2 , 16 не получишь ... имеется в виду в какую степень возвести 2 ж, откуда тут 1

[@Cronis]

a wakeup call спасибо за вопрос! Вот пример: 1 * 2 * 2 * 2 *2 = 16. Сколько раз необходимо умножить единицу на двойку? 4 раза

[@PaladinProg]

Спасибо большое, теперь стало понятнее

[@kirill4531]

17:16 Сколько раз нужно умножить 1 на 2 чтобы получить 16? Почему 4? 1) 1х2 = 2 2) 1х2 = 2 3) 1х2 = 2 4) 1х2 = 2 ------------ 8 8 =/= 16

[@Cronis]

1*2*2*2*2 мы умножили 1 на двойку 4 раза

[@kirill4531]

@@Cronis это я понял, просто я считаю что формулировка задания некорректная. Сколько раз умножить 1 на 2 И На Результат (или как-то так) будет более правильно. А то сколько раз умножить 1 на 2 подразумевает последующее сложение результата

[@Cronis]

Почему подразумевает?

[@АндрейЧернов-ь2ш]

В 12:46 говорится, что N^2 больше в два раза чем N. Но это бред! В два раза больше - это 2*N, а N^2 - это больше N в N раз. Да и в целом, учитывая оговорки и некорректные высказывания, указанные ниже в комментариях, можно сделать вывод, что к такому лектору на эти курсы ходить не стоит. Хотя в целом видео заслуживает внимания.

[@Cronis]

Андрей Чернов, спасибо за комментарий! Возможно вы не расслышали, что было сказано: эн квадрат __больше__ чем в два раза превышает эн. Поэтому мы говорим, что эн квадрат намного больше эн.

[@АндрейЧернов-ь2ш]

Переслушал еще раз. И опять слышу то, что написал выше. Дословно то, что говорится в видео: "Значительно - это значит в два раза. Если эн в два раза больше другого числа эм, значит эн значительно больше чем эм". Я понял, что хотел сказать лектор, но это прозвучало на фоне объяснения почему N^2 значительно больше N. Вот как раз слов "эн квадрат _больше_ чем в два раза превышает эн" сказано не было. Поэтому возникает путаница.

[@nalilata]

@@Cronis извините, а зачем нам это "N^2 значительно больше N" если чтобы его отбросить, достаточно того, что N не больше N^2. мы даже строчкой выше N^2 отбросили, к чему такая возня с N, если мы его отбросим, в 2 раза оно меньше N^2 или даже в 1? и дальше 18:28 "или N + log N" - log N же отбрасывается?

[@hello_world_zz]

Препод супер, в стиле Грокаем Алгоритмы

[@Daoway-f7o]

не понял почему на 8:08 функция рекурсивная и почему выполняться будет 10 или 100 раз. там просто линейное вычисление!

[@Cronis]

При n равном 10 она будет выполняться 10 раз, а при n равном 100 - 100 раз. Все верно. Это и есть линейная сложность. Не совсем понимаю ваш вопрос.

[@Daoway-f7o]

@@Cronis спасибо, разобрался. там метод вызывает сам себя. и делает это несколько раз. это не относится к интерфейсу Iterable, но принцип тот же по коду

[@johnwhite9906]

int sum(int n) { if (n == 1) return 1; return n + sum (n - 1); } Выдает ошибку, почему? File "", line 1 int sum(int n) { ^ SyntaxError: invalid syntax

[@Cronis]

Это же не питон :)

[@garikspiridonov3869]

21:13 Квадрат не стал на половину меньше, он стал меньше, приблизительно на одну треть. Хотя согласен с вами, как следует из вашего обьяснения это не важно.

[@Cronis]

Вы правы, там не совсем половина, а меньше. Но каквы и сказали, мы игнорируем константы :)

[@iakovryzhichka2832]

Спасибо за видео! Надеюсь поможет на собеседовании. Может уже спрашивали, но попытаю счастье. Вот не учитываются константы для оценки сложности. Это если у нас бесконечное число операций, то да, но на практике если я пройдусь по конечному массиву за одну секунду, то по идее полмассива я пройду за полсекунды. И если стоит задача оптимизации, то константы тоже важны, верно?

[@Cronis]

Ответ очень очень длинный. Коротко - оценке сложности не показывает точно сложность, а примерную. И на такие мелочи как константы никто не обращает внимание. Под видео есть ссылка на полный курс по оценке сложности, там первые 40 минут подробно рассказывается про константы и как что работает

[@ИгнатМирзализадэ]

Дополню. Big O от слова Порядок (Ordnung)

[@games4us132]

Спасибо, помогли разобраться.

[@31more]

Почему в разборе первого алгоритма говорится, что функция вызывается n раз, ведь нет присваивания n:=n-1?

[@Cronis]

Подскажите, на какой минуте разбирается алгоритм?

[@reddragons9979]

Офигенное видео)

[@Cronis]

Спасибо!

[@ЕрвандАгаджанян-в3к]

Время на видео 22:05 разве не A^2 * B? Там же 3 цикла. И 2 из их - одинаковые (они и будут A^2). А 3-й будет B. Не так?

[@Cronis]

Добрый день, Ерванд! Первый цикл выполняется А раз, вложенный в него -- В раз, а вложенный в него -- 100000 раз. Итого получаем: A * B * 100000 = O(A * B)

[@nano28950]

Лучший!

[@maksimsergeevich5939]

Спасибо за видео!

[@marlonbrando458]

Спасибо, лайк!

[@korsman723]

Здравствуйте, Немного непонятноm почему O(N² + N) будет равен O(N²), разве не O(N³) должно получиться? Это же базовое сложение, и пренебрегать этим - уже нарушение всей логики

[@Cronis]

Вы перепутали умножение со сложением: N*N^2 = N^3

[@sergpoltr2686]

Хорошо рассказываете

[@SuperSonicLeader]

спасибо, хорошее видео, лайк!

[@taboollive727]

Насколько я понял в примере 3 - нужно учитывать дополнительно 4 наружных цикла, если бы он был заполнен кодом. Тогда было бы 16 + 4. O(N² + √N) - так можно было бы записать, если наружный for тоже вызывал бы метод foo()? И по моему sortString сортирует не строки а массивы char в строках? Просто фразу не понял.

[@Cronis]

Не понял вопрос. В третьем примере сложность O(N^2) т.к. foo выполнится N + (N-1) + (N-2) + ... + 2 + 1 = N(N+1)/N = O(N^2) раз. Это арифметическая прогрессия

[@bor4963]

Хорошо! Нет понятия порядок функции. Тогда легко перейдете от =n к квадрату n

[@ВадимЛадик-т7м]

Поправьте, если ошибся. На 9.30 у рекурсивной функции сложность О(1), пожалуй не соглашусь. Попробуйте выполнить эту функцию с х=50, там скорее квадратичная зависимость О(n2). И ещё интересен случай, если подать на вход 0)

[@Cronis]

Тело функции выполняется за O(1) т.к. не зависит от N. Но выполнятся это самое тело N раз. Поэтому сложность итоговая равна O(N)

[@xfgweb]

Подскажите правильно ли я оценил сложность алгоритма gist.github.com/xfg/3f91181e14c20239affefc218d430edf ? Здесь рекурсия в цикле, которая перебирает объект, в который могут быть вложены другие объекты. У меня получилась сложность O(N * A) насколько я понимаю, это хуже, чем O(N) но всё еще намного лучше, чем O(N * N)

[@Cronis]

При наличии цикла сложность будет описываться как O(A^N) из-за дерева рекурсивных вызовов

[@xfgweb]

@@Cronis спасибо.

[@nighthoves7212]

частично поняла суть, но по сравнению с тем, что я смотрела в инете чтобы понять данную тему - это лучшее

[@Cronis]

Спасибо!

[@Das.Kleine.Krokodil]

Видео отличное. Правда бинарный поиск можно было нагляднее показать графически: отрезками, деревом или еще как то

[@masterswift9700]

Курс на юдеми не бесплатный сейчас?

[@Cronis]

Добрый день, курс на udemy сейчас со скидкой 88%

[@vip51000]

@@Cronis какой курс, дайте ссылку

[@Cronis]

@@vip51000 держите www.udemy.com/course/big-o-ru/?referralCode=BC5F6819EE463A685AE3

[@vip51000]

@@Cronis спасибо

[@pansiarhei]

Спасибо, хорошее видео

[@awakeupcall5336]

ну окей мы имеем O (L * N * (logL + logN)) - это сильно плохо? какие рекомендации, как избегать сложности алгоритма, кроме того, что быть внимательным к вложенным циклам?

[@Cronis]

Быть внимательным. Если бы была формула идеального кода, его бы писали роботы, и программисты были бы не нужны :)

[@rodgenk]

Здорово, спасибо.

[@ЕрвандАгаджанян-в3к]

Очень круто

[@zukora]

Дякую, годно!

[@Cronis]

Пожалуйста

[@raimbektoleugaziev4845]

Почему пример со сложностью О(А*В) не является О(n^2) ?

[@Cronis]

Raimbek Toleugaziev т.к. это разные переменные

[@6rk5h]

11:06, мне кажется, что сколько раз 1 на 2 не умножай, всегда 2 выходит.

[@Cronis]

1*2*2*2*2 мы умножили единицу на два 4 раза :)

[@6rk5h]

@@Cronis мы умножили 1 на 2 один раз, потом умножили 2 на 2 один раз, потом 4 на 2 и 8 на 2 по разу

[@MagicMightNew]

На 18:01, мне кажется, не совсем корректно построено объяснение. Мы не пишем 2 в основании логарифма не потому, что оно является константой, которые не играют роли в оценке сложности, а потому что мы условились, что будем считать обозначение log - логарифмом по основанию 2.

[@Cronis]

Спасибо за комментарий! Подробное доказательство здесь: pp.userapi.com/c621509/v621509433/749bf/P2WnzUsPw3k.jpg

[@MagicMightNew]

Да, я еще раз пересмотрел ту часть видео. На самом деле моя ошибка, Вы действительно были правы)

[@derzhavin_d]

Хочу поставить 10 тысяч лайков автору

[@Cronis]

Расскажите о канале друзьям, это будет реальная польза мне)

[@alionabelomenova1075]

Огромное спасибо, очень последовательно и понятно.

[@Cronis]

Был рад помочь!

[@Daoway-f7o]

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

[@Cronis]

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

[@Daoway-f7o]

@@Cronis ну хорошо. а вот допустим про коллекции точно спросят. а потом вопрос - почему одни быстрее других. Или такой вопрос задать - какая оценка временной сложности выборки элемента из HashMap? Или же у джунов такое обычно не спрашивают? Заранее спасибо за ответ

[@Cronis]

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

[@nikolaysokolov9027]

Отличное видео. Спасибо большое!

[@МихаилХолостов-р1п]

13:51 такая функция называется показательная

[@hikkariwest5078]

Аааа... Под конец мало что понятно... Как понять что он вложенный?

[@Cronis]

Уточните, пожалуйста, про какое время видео идет речь

[@alex_mech]

Мне кажется, было бы попроще начать не сразу с концепции bigO, а с математической основы smallO и bigO как верхнего и нижнего пределов ряда. Тогда не пришлось бы оправдываться словами в стиле «что такое О? Это условное обозначение концепции bigO”, которое снимает очевидный вопрос, но порождает следующий - «а почему большое О, что, есть маленькая О?». Концепция пришла из матанализа, так и стоило для порядка к нему обратиться, хотя бы в базовой форме

[@Cronis]

Под видео есть ссылка на мой полный курс по оценке сложности со всеми математическими выкладками, теорией множеств и всем, всем, всем. Здесь видео для широкой публики, поэтому такой язык. Если хотите серьезно изучить - посмотрите курс, вопросов не останется :)

[@andrejermolenko8813]

Не пойму, почему при О(N) быстродействие программы ПРЯМОпропорционально N, когда оно ОБРАТНОпропорционально. Или автор оговорился либо я настолько тупой

[@Cronis]

Чем больше входные параметры, тем больше N Прямая пропорциональность

[@andrejermolenko8813]

@@Cronis причем тут входные данные? На 9 минуте сказано- между "быстродействием программы" и ростом N прямая пропорциональность. N это и есть, в каком то смысле входные данные, т.к в примере от него НАПРЯМУЮ зависит глубина рекурсии, а значит и ВРЕМЯ ВЫПОЛНЕНИЯ программы. Вот оно то - это время как раз прямопропорционально росту N. Автор просто, оговорился возможно, возможно, он и имел ввиду "время выполнения", а сказал "быстродействие". А это вещи абсолютно противоположные

[@СергейЩербак-о3н]

Сколько раз нужно умножить 1 на 2 что бы получить 16 ? Если только умножать то в результате всегда будет 2.

[@Cronis]

Спасибо за просмотр! Фраза означает: 1 * 2 * 2 * 2 * 2 = 16 то есть мы должны 4 раза умножить 1 на 2 чтобы получить 16

[@СергейЩербак-о3н]

Курсы Cronis, спасибо за ответ! Хорошо обьясняете не усложняя простые вещи, цветовая гамма видео хорошо подобрана, приятно смотреть не напрягает.