На 13:50 говорится: "На самом деле степенная функция растет гораздо быстрее N в степени 100. Таким образом ответ будет O(2^n)" Допущена ошибка, т.к N^100 - это и есть степенная функция.
Правильнее было бы сказать, что можно доказать, что показательная функция на бесконечности растет быстрее степенной, вот и все. А так - да, большое спасибо за видео!
Разбор темы сложности алгоритмов отличный. Супер. Долго не мог разобраться, скитался по интернету, а оказалось есть одно видео, которое за 25 минут излагает максимум полезной информации. Спасибо
Полезная информация начинается где то с 6 минуты. Хотел уж было бросить смотреть, но слава богу не бросил. Полезная информация на самом деле полезная. Очень хорошо и понятно все объяснено, спасибо большое.
Количество тактов процессора не равно количеству шагов для выполнения алгоритма. Ибо количество тактов зависит от количества и типов машинных кодов, а компиляция одного и того же алгоритма разными компиляторами или для разных процессоров будет давать разный набор машинных кодов.
Спасибо вам! Проходил курсы от Яндекса по алгоритмам, где объясняли big O, но ничего не понял, а вы очень доходчиво и подробно объяснили. Ещё раз спасибо!
Спасибо зо подробное и доходчивое объяснение ключевых базовых понятий. 25 минут видео я посмотрел за час - прорешивал, записывал. Не знаю было ли где-то в комментах, но меня покоробила фраза на 17.11 - "сколько раз нужно умножить 1 на 2 чтобы получить 16?" мой ответ 8. потому как 1*2+1*2+1*2+1*2=8 а не 4. Но, в общем понятно что имелось в виду.
Спасибо! отличные примеры из жизни. Очень наглядно! на 13:57 нагляднее пожалуй сравнивать 2^N and N^2. И первый график будет расти быстрее, намного быстрее второго, поэтому второй можно отбросить.
7:06, при передаче на самолёте размер передаваемых файлов не увеличивается, то есть по оси "Количество бит" нет изменения, меняется только время полёта, в зависимости от погодных условий и скорости самолёта. Прямая должна быть вертикальной. Тогда это конечно будет менее наглядно, но оси можно поменять местами и всё будет ok.
В видео говорится, что мы сортируем строки длиной L. В любой сортировке есть всегда код вида if(str1 > str2). А сравнение строк одинаковой длины L -- это сравнение их L символов. Следовательно, мы умножаем сложность сортировки на L
Я не очень сведущ в языках но на 19:11 в цикле скобки разные стоят[) потому сложность будет 0. Видос конечно супер щикарный, с примерами, по делу, без тормозов. Респект!
12:43 n< n^2 , n -> inf не тому, що в 2 рази більша друга функція (вона взагалі в n раз більша) , а тому , що похідна другої функції рівна 2n , а першої 1, отже inf > 1, тому і нехтуємо.
21:13 Квадрат не стал на половину меньше, он стал меньше, приблизительно на одну треть. Хотя согласен с вами, как следует из вашего обьяснения это не важно.
В примере 3 было сказано, что сложность алгоритма N^2, но если посмотреть внимательнее, то N(N-1)(N-2)...1 это Nфакториал. Тоесть будет О(N!). И если смотреть по квадрату 4х4,то отсекается не половина, а немного меньше половины, что, логично предположить, будет О(nlogn). И если расписывать эти два случая, то мы получим равенство сложностей N! =~ NLogN. Если в чем-то не прав, то поправьте пожалуйста
Не понятно в 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 Только начал вариться в этой теме, может тут как-то по другому работает
7:28 Как это O(0) означает, что ничего не происходит? O(0) означает, или что для выполнения задачи не требуется выполнять каких либо действий, или что количество операций для выполнения задания уменьшается с ростом сложности задачи асимптотически к нулю. Раньше же сказано, что оценка верхней границы не зависит от времени, а значит говорить, что-то что-то происходит или не происходит не корректно.
Вы полностью правы. Но как это все сказать для простого человека, который впервые это видит и не напугать его сложными формулировками? :) поэтому вот просто и сказано - суть отражает и не пугает. Под видео есть ссылка на оценку сложности со строгой математикой и с теорией множеств на 2.5 часа. Там мы рассказываем уже все четко для тех, кому нужна математическая строгость. А здесь для широкого зрителя :)
Спасибо за видео! Надеюсь поможет на собеседовании. Может уже спрашивали, но попытаю счастье. Вот не учитываются константы для оценки сложности. Это если у нас бесконечное число операций, то да, но на практике если я пройдусь по конечному массиву за одну секунду, то по идее полмассива я пройду за полсекунды. И если стоит задача оптимизации, то константы тоже важны, верно?
Ответ очень очень длинный. Коротко - оценке сложности не показывает точно сложность, а примерную. И на такие мелочи как константы никто не обращает внимание. Под видео есть ссылка на полный курс по оценке сложности, там первые 40 минут подробно рассказывается про константы и как что работает
В 12:46 говорится, что N^2 больше в два раза чем N. Но это бред! В два раза больше - это 2*N, а N^2 - это больше N в N раз. Да и в целом, учитывая оговорки и некорректные высказывания, указанные ниже в комментариях, можно сделать вывод, что к такому лектору на эти курсы ходить не стоит. Хотя в целом видео заслуживает внимания.
Андрей Чернов, спасибо за комментарий! Возможно вы не расслышали, что было сказано: эн квадрат __больше__ чем в два раза превышает эн. Поэтому мы говорим, что эн квадрат намного больше эн.
Переслушал еще раз. И опять слышу то, что написал выше. Дословно то, что говорится в видео: "Значительно - это значит в два раза. Если эн в два раза больше другого числа эм, значит эн значительно больше чем эм". Я понял, что хотел сказать лектор, но это прозвучало на фоне объяснения почему N^2 значительно больше N. Вот как раз слов "эн квадрат _больше_ чем в два раза превышает эн" сказано не было. Поэтому возникает путаница.
@@Cronis извините, а зачем нам это "N^2 значительно больше N" если чтобы его отбросить, достаточно того, что N не больше N^2. мы даже строчкой выше N^2 отбросили, к чему такая возня с N, если мы его отбросим, в 2 раза оно меньше N^2 или даже в 1? и дальше 18:28 "или N + log N" - log N же отбрасывается?
Здравствуйте, почему 16:20 говорится, что мы должны искать число сначала в 16 элементах, если мы уже делим его на два? то есть, мы ищем в 8 элементах, немного не понял момент.
Здравствуйте, спасибо за видео! Есть один вопрос. На 20:05 вы говорите, что сложность алгоритма будет ровна О(N+(N-1)+(N-2)+...+2+1). Не совсем понятно почему вы складываете кол-во операций, ведь в предыдущем примере с вложенным циклом, сложность алгоритма ровнялась О(N*N). Разве тут не должно было получится, что сложность алгоритма ровняется О(N*N+N(N-1)+N(N-2)+...+2N+N?
Добрый день! Смотрите: в первом цикле i = 0, то есть второй цикл идёт от j = 0 до N. Затем i = 1 то есть второй цикл идёт от j = 1 до N затем второй цикл идёт от j = 2 до N. Следуя этой логике, получаем N+(N-1)+(N-2)+...+2+1
@@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), но описание как его получили в видео не правильное.
@@Cronis тут вы не правы, из N+(N-1)+(N-2)+...+2+1 никак не вывести N^2, следовательно, как и писали выше правильная запись будет вида N*(N+(N-1)+(N-2)+...+2+1)
@@Cronis это я понял, просто я считаю что формулировка задания некорректная. Сколько раз умножить 1 на 2 И На Результат (или как-то так) будет более правильно. А то сколько раз умножить 1 на 2 подразумевает последующее сложение результата
Подскажите пожалуйста, если формула расчета кол-ва итераций для алгоритма сортировки равна - n*(n/10) то какая здесь сложность получается? O(n) или O(n^2) ? Должен ли я отбросить n/10 так как это "n" становится в 10 раз меньше другого n. Или правильней будет отбросить знаменатель 10, тогда получится, что у нас остается n^2. Как правильно? Я не понимаю... Если ответите, сразу поясните пожалуйста, почему должен быть именно такой ответ. Или в видео неточность? Может правильное сказать, что незначительное n это не то которое более чем в 2 раза больше, а то которое меньше на степень другого n?
Добрый день! Здесь сложность N^2 т.к. мы отбрасываем константы все, а 10 это констатнта. Правило очень простое -- все что константа сразу отбрасывается, а из оставшихся слагаемых выбирается то, у которого выше скорость роста (еще называют порядок). Градация по убыванию: N! -> 2^N -> N^2 -> N * log N -> N -> SQRT(N) -> log N -> 1
@@Cronis спасибо, разобрался. там метод вызывает сам себя. и делает это несколько раз. это не относится к интерфейсу Iterable, но принцип тот же по коду
17:17 смущает запись "сколько раз умножить 1 на 2 чтобы получить 16?" сколько раз не умножай 1 на 2 , 16 не получишь ... имеется в виду в какую степень возвести 2 ж, откуда тут 1
Поправьте, если ошибся. На 9.30 у рекурсивной функции сложность О(1), пожалуй не соглашусь. Попробуйте выполнить эту функцию с х=50, там скорее квадратичная зависимость О(n2). И ещё интересен случай, если подать на вход 0)
Насколько я понял в примере 3 - нужно учитывать дополнительно 4 наружных цикла, если бы он был заполнен кодом. Тогда было бы 16 + 4. O(N² + √N) - так можно было бы записать, если наружный for тоже вызывал бы метод foo()? И по моему sortString сортирует не строки а массивы char в строках? Просто фразу не понял.
Не понял вопрос. В третьем примере сложность O(N^2) т.к. foo выполнится N + (N-1) + (N-2) + ... + 2 + 1 = N(N+1)/N = O(N^2) раз. Это арифметическая прогрессия
Добрый день, Ерванд! Первый цикл выполняется А раз, вложенный в него -- В раз, а вложенный в него -- 100000 раз. Итого получаем: A * B * 100000 = O(A * B)
Здравствуйте, Немного непонятноm почему O(N² + N) будет равен O(N²), разве не O(N³) должно получиться? Это же базовое сложение, и пренебрегать этим - уже нарушение всей логики
На самом деле log2N это будет когда мы будем точно делить список(массив) попалам на каждой итерации но мы можем же делить на 3, 4 и тд частей и уже не получится логарифм с основанием 2 поэтому в видео есть неточности. Основа логарифма отбрасывается не из-за того что это константа а из-за того что деление списка может быть больше чем на 2 части
Спасибо за комментарий! Основание логарифма это константа. Доказательство это свойство 13: 2.bp.blogspot.com/-RFm5xlyqFf0/WuBL2YudoEI/AAAAAAAAByk/tRjvR5l7FvkB_ylwBEPEh_8x63UTxW8kwCLcBGAs/s1600/009.jpg По поводу как он образуется: именно деление объекта пополам дает основание 2. Если бы вы делил на части 25% и 75%, было бы основание 4/3. Что тоже константа
@@manOfPlanetEarth неуч то ты, я смотрел этот весь бред по сложность алгоритмов и подобную пургу только ради интереса, не более. Я понял, что все это бесполезные вещи, потому что у меня есть друг с которым каждый день общаюсь, он недавно закончил стажировку в гугле, сам сказал что пободные хрени не пригодились в самом гугле, что его очень сильно удивило. Учи дальше этот бред никому не нужный (деньги оно тебе не принесет, баран)😱
Мне кажется, было бы попроще начать не сразу с концепции bigO, а с математической основы smallO и bigO как верхнего и нижнего пределов ряда. Тогда не пришлось бы оправдываться словами в стиле «что такое О? Это условное обозначение концепции bigO”, которое снимает очевидный вопрос, но порождает следующий - «а почему большое О, что, есть маленькая О?». Концепция пришла из матанализа, так и стоило для порядка к нему обратиться, хотя бы в базовой форме
Под видео есть ссылка на мой полный курс по оценке сложности со всеми математическими выкладками, теорией множеств и всем, всем, всем. Здесь видео для широкой публики, поэтому такой язык. Если хотите серьезно изучить - посмотрите курс, вопросов не останется :)
Подскажите правильно ли я оценил сложность алгоритма gist.github.com/xfg/3f91181e14c20239affefc218d430edf ? Здесь рекурсия в цикле, которая перебирает объект, в который могут быть вложены другие объекты. У меня получилась сложность O(N * A) насколько я понимаю, это хуже, чем O(N) но всё еще намного лучше, чем O(N * N)
Не корректно так говорить, т.к. сколько бы мы раз не умножали 1 на 2 результат всегда будет 2. Правельно вопрос будет звучать так: в какую степень нужно возвести 2, чтобы получить 16
Скажите пож-та на позицию джуна тоже любят спрашивать такие вопросы? Не имею в виду серьезные компании типа google, а компании среднего уровня. что еще любят спрашивать по алгоритмам - так понял поиск в массиве и бинарный поиск?
@@Cronis ну хорошо. а вот допустим про коллекции точно спросят. а потом вопрос - почему одни быстрее других. Или такой вопрос задать - какая оценка временной сложности выборки элемента из HashMap? Или же у джунов такое обычно не спрашивают? Заранее спасибо за ответ
ну окей мы имеем O (L * N * (logL + logN)) - это сильно плохо? какие рекомендации, как избегать сложности алгоритма, кроме того, что быть внимательным к вложенным циклам?
18:04 > автор не знает математику: "Log N" это и означает что логарифм по основанию 2. 2 - это основание логарифма и в данном примере "является константой которую можно выбросить" это просто не имеет смысла. Само основание важно ибо если оно меньше 1 то ф-я убывающая в записи bigO опускается 2 но оно всегда подразумевается
На 13:50 говорится: "На самом деле степенная функция растет гораздо быстрее N в степени 100. Таким образом ответ будет O(2^n)"
Допущена ошибка, т.к N^100 - это и есть степенная функция.
Спасибо! Оговорился :)
Правильнее было бы сказать, что можно доказать, что показательная функция на бесконечности растет быстрее степенной, вот и все. А так - да, большое спасибо за видео!
@@ic6406 да, действительно n^100 растет быстрее (когда n - небольшое число), чем 2^n. А так они очень похожи
@@ic6406 если рассмотреть функцию f(x)=2^x/x^10, видно что при x~100 f(x)>1, соответственно, показательная функция растет быстрее при x->inf
@@ic6406 любая экспоненциальная функция растет быстрее чем полином.
Спасибо, благодаря вашему видео у меня сложилось хоть какое-то понятие о "Big O".
Просто бомба! Долго боялся взяться разузнать что такое сложность алгоритмов. Тут всё лаконично и объясняется до самого основания. Большое спасибо)
Разбор темы сложности алгоритмов отличный. Супер. Долго не мог разобраться, скитался по интернету, а оказалось есть одно видео, которое за 25 минут излагает максимум полезной информации. Спасибо
Никита Лобаев, спасибо! Был рад помочь!
Дело говорит, твое видео самое полезное на эту тему во всем интернете. Большое спасибо за твой труд)
Это материал по книге для подготовки к интервью CRACKING CODING INTERVIEW 189 PROGRAMMING Questions & SOLUTIONS
Читайте описание видео)
Очень редко оставляю коментарии, но тут все заслужено. Пожалуй, лучшее объяснение, что я встречал.
Очень понятно и доступно, все разложено по полочкам. Хотя и понятно, что это лишь вершина айсберга. Огромное спасибо автору!!!
Полезная информация начинается где то с 6 минуты. Хотел уж было бросить смотреть, но слава богу не бросил. Полезная информация на самом деле полезная. Очень хорошо и понятно все объяснено, спасибо большое.
Рад, что досмотрели :)
Количество тактов процессора не равно количеству шагов для выполнения алгоритма. Ибо количество тактов зависит от количества и типов машинных кодов, а компиляция одного и того же алгоритма разными компиляторами или для разных процессоров будет давать разный набор машинных кодов.
Сергей, вы абсолютно правы. К сожалению сделали ошибку при записи :(
спасибо, человеческим языком и доходчиво. Наконец-то кто-то это сделал
Огромное спасибо, всё ПРЕДЕЛЬНО понятно!
Спасибо! :)
Спасибо вам! Проходил курсы от Яндекса по алгоритмам, где объясняли big O, но ничего не понял, а вы очень доходчиво и подробно объяснили. Ещё раз спасибо!
Рад помочь!
Спасибо огромное за видео ! Все так понятно, особенно на конкретных примерах 💙
Спасибо за комментарий!
Просто супер, спасибо!!! Отдельное спасибо за примеры
Всегда рад помочь!
Отличный и подробный разбор, качественное объяснение материала, спасибо большое
Отличное видео и курс! Спасибо!
Рад помочь!
Сложно очень воспринимать с первого раза XD. С 4 раза понял что да как. Объясняете очень хорошо спасибо за видео.
Реально спасибо за понятное объяснение....😁
Очень хорошее разъяснение - лучшее, что я видел.
Рад помочь!
Спасибо зо подробное и доходчивое объяснение ключевых базовых понятий. 25 минут видео я посмотрел за час - прорешивал, записывал.
Не знаю было ли где-то в комментах, но меня покоробила фраза на 17.11 - "сколько раз нужно умножить 1 на 2 чтобы получить 16?" мой ответ 8. потому как 1*2+1*2+1*2+1*2=8 а не 4.
Но, в общем понятно что имелось в виду.
1*2*2*2*2=16
@@Roomaa111 хех, класс!
@@Roomaa111 на сколько двоек нужно умножить единицу
Спасибо. В общих чертах стало понятно.
Спасибо! отличные примеры из жизни. Очень наглядно! на 13:57 нагляднее пожалуй сравнивать 2^N and N^2. И первый график будет расти быстрее, намного быстрее второго, поэтому второй можно отбросить.
Благодарю! Желаю вам всего самого наилучшего просто вау! ВСЕ ПОНЯТНООО!!!))
Лучшее объяснение, что видел вообще.
Очень полезное видео для старта в изучении сложности алгоритмов!
пожалуй лучшее!
теперь можно приступать к "грокаем алгоритмы"
Спасибо! Грокаем алгоритмы -плохая, поверхностная книга, которая путает больше, чем помогает.
@@Cronis спасибо! Учту!
7:06, при передаче на самолёте размер передаваемых файлов не увеличивается, то есть по оси "Количество бит" нет изменения, меняется только время полёта, в зависимости от погодных условий и скорости самолёта. Прямая должна быть вертикальной. Тогда это конечно будет менее наглядно, но оси можно поменять местами и всё будет ok.
При росте количеств бит время не меняется. График верный
Большое спасибо за видео. Лично для меня тема стала понятнее.
Приходите к нам на интенсив, узнаёте ещё больше: ua-cam.com/video/FhS5IeCL8OU/v-deo.html
Спасибо за такие простые обьяснения, подписка!
Круто, очень живо и ясно. Огромное спасибо!
Спасибо, было познавательно
22:58 подскажите, откуда с неба взяли L * log L ?
В видео говорится, что мы сортируем строки длиной L. В любой сортировке есть всегда код вида if(str1 > str2). А сравнение строк одинаковой длины L -- это сравнение их L символов. Следовательно, мы умножаем сложность сортировки на L
Спасибо, все лаконично, кратко и понятно!
Я не очень сведущ в языках но на 19:11 в цикле скобки разные стоят[) потому сложность будет 0. Видос конечно супер щикарный, с примерами, по делу, без тормозов. Респект!
Спасибо ,очень информативно и доступно!
Бро ты крут! Лайк однозначно. Пошел дальше готовиться к собеседованию в фейсбук
12:43
n< n^2 , n -> inf не тому, що в 2 рази більша друга функція (вона взагалі в n раз більша) , а тому , що похідна другої функції рівна 2n , а першої 1, отже inf > 1, тому і нехтуємо.
Спасибо от души!
На здоровье)
21:13 Квадрат не стал на половину меньше, он стал меньше, приблизительно на одну треть. Хотя согласен с вами, как следует из вашего обьяснения это не важно.
Вы правы, там не совсем половина, а меньше. Но каквы и сказали, мы игнорируем константы :)
16:59 Сколько раз нужно умножить 1 на 2 чтобы получить 16? В целом ход лекции мне нравится. Но вот бы поправили несколько ошибок...
1*2*2*2*2 = 16 сколько раз вы умножили 1 на 2 чтобы получить 16?
Отличное разъяснение, спасибо!
Скажите, пожалуйста, а почему сортировка строки L*Log_L?
Встроеннная в язык сортировка это сонтировка quicksort. Ей мы и сортируем строки. И ее сложность O(L * logL)
@@Cronis это бы совершенно неочевидно)
Офигенное видео!!! Большое спасибо автору!
Супер круто, спасибо огромное, очень понятно и информативно, просто бомба
Спасибо за добрые слова!
Очень хорошее и познавательное видео
Спасибо!
В примере 3 было сказано, что сложность алгоритма N^2, но если посмотреть внимательнее, то N(N-1)(N-2)...1 это Nфакториал. Тоесть будет О(N!). И если смотреть по квадрату 4х4,то отсекается не половина, а немного меньше половины, что, логично предположить, будет О(nlogn). И если расписывать эти два случая, то мы получим равенство сложностей N! =~ NLogN. Если в чем-то не прав, то поправьте пожалуйста
будет:
N + (N - 1) + (N - 2) .... + 3 + 2 + 1 = N(N+1)/2 = O(N^2)
В треугольнике тоже кружки идут как 4 + 3 + 2 + 1 = 4*(4+1)/2 = 10
А почему на 24:12 сложность сортировки строки log(l) ?
Сложность написана L * log (L)
Спасибо за урок!
Не понятно в 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
Только начал вариться в этой теме, может тут как-то по другому работает
Просто вынесли за скобки N * L.
То есть не вашем примере 2 + 2 * 2 = 2 * (1 + 1 * 2)
@@Cronis Спасибо🙏 3 года прошло, а ответ за сутки, респект)
7:28 Как это O(0) означает, что ничего не происходит? O(0) означает, или что для выполнения задачи не требуется выполнять каких либо действий, или что количество операций для выполнения задания уменьшается с ростом сложности задачи асимптотически к нулю. Раньше же сказано, что оценка верхней границы не зависит от времени, а значит говорить, что-то что-то происходит или не происходит не корректно.
Вы полностью правы. Но как это все сказать для простого человека, который впервые это видит и не напугать его сложными формулировками? :) поэтому вот просто и сказано - суть отражает и не пугает. Под видео есть ссылка на оценку сложности со строгой математикой и с теорией множеств на 2.5 часа. Там мы рассказываем уже все четко для тех, кому нужна математическая строгость. А здесь для широкого зрителя :)
Спасибо за видео! Надеюсь поможет на собеседовании. Может уже спрашивали, но попытаю счастье. Вот не учитываются константы для оценки сложности. Это если у нас бесконечное число операций, то да, но на практике если я пройдусь по конечному массиву за одну секунду, то по идее полмассива я пройду за полсекунды. И если стоит задача оптимизации, то константы тоже важны, верно?
Ответ очень очень длинный.
Коротко - оценке сложности не показывает точно сложность, а примерную. И на такие мелочи как константы никто не обращает внимание. Под видео есть ссылка на полный курс по оценке сложности, там первые 40 минут подробно рассказывается про константы и как что работает
В 12:46 говорится, что N^2 больше в два раза чем N. Но это бред! В два раза больше - это 2*N, а N^2 - это больше N в N раз. Да и в целом, учитывая оговорки и некорректные высказывания, указанные ниже в комментариях, можно сделать вывод, что к такому лектору на эти курсы ходить не стоит. Хотя в целом видео заслуживает внимания.
Андрей Чернов, спасибо за комментарий! Возможно вы не расслышали, что было сказано: эн квадрат __больше__ чем в два раза превышает эн. Поэтому мы говорим, что эн квадрат намного больше эн.
Переслушал еще раз. И опять слышу то, что написал выше. Дословно то, что говорится в видео: "Значительно - это значит в два раза. Если эн в два раза больше другого числа эм, значит эн значительно больше чем эм". Я понял, что хотел сказать лектор, но это прозвучало на фоне объяснения почему N^2 значительно больше N. Вот как раз слов "эн квадрат _больше_ чем в два раза превышает эн" сказано не было. Поэтому возникает путаница.
@@Cronis извините, а зачем нам это "N^2 значительно больше N" если чтобы его отбросить, достаточно того, что N не больше N^2. мы даже строчкой выше N^2 отбросили, к чему такая возня с N, если мы его отбросим, в 2 раза оно меньше N^2 или даже в 1?
и дальше 18:28 "или N + log N" - log N же отбрасывается?
Здравствуйте, почему 16:20 говорится, что мы должны искать число сначала в 16 элементах, если мы уже делим его на два? то есть, мы ищем в 8 элементах, немного не понял момент.
Сначала в массиве 16 элементов, потом 8, потом 4, потом 2, потом 1.
Поэтому мы сначала ищем среди 16 элементов
Огромное Спасибо! Наконец-то понял что такое big O !!! 2019 !!!
Здравствуйте, спасибо за видео! Есть один вопрос. На 20:05 вы говорите, что сложность алгоритма будет ровна О(N+(N-1)+(N-2)+...+2+1). Не совсем понятно почему вы складываете кол-во операций, ведь в предыдущем примере с вложенным циклом, сложность алгоритма ровнялась О(N*N). Разве тут не должно было получится, что сложность алгоритма ровняется О(N*N+N(N-1)+N(N-2)+...+2N+N?
Добрый день! Смотрите: в первом цикле i = 0, то есть второй цикл идёт от j = 0 до N. Затем i = 1 то есть второй цикл идёт от j = 1 до N затем второй цикл идёт от j = 2 до N. Следуя этой логике, получаем N+(N-1)+(N-2)+...+2+1
@@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), но описание как его получили в видео не правильное.
@@Cronis тут вы не правы, из N+(N-1)+(N-2)+...+2+1 никак не вывести N^2, следовательно, как и писали выше правильная запись будет вида N*(N+(N-1)+(N-2)+...+2+1)
@@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
@@Cronis Ок, понял, тоесть не во всех случаях когда видим вложенный цикл нужно подразумевать перемножение сложностей, как было сказано ранее в видео?
Спасибо, лайк!
Спасибо большое, теперь стало понятнее
Больше спасибо, но ничего не понятно, log N получается в половину меньше чем N и в меньше чем N^2 ?
Хорошо! Нет понятия порядок функции. Тогда легко перейдете от =n к квадрату n
Офигенное видео)
Спасибо!
А про бинарный поиск не проще корень квадратный от N ?
Спасибо, помогли разобраться.
Препод супер, в стиле Грокаем Алгоритмы
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
1*2*2*2*2 мы умножили 1 на двойку 4 раза
@@Cronis это я понял, просто я считаю что формулировка задания некорректная.
Сколько раз умножить 1 на 2 И На Результат (или как-то так) будет более правильно.
А то сколько раз умножить 1 на 2 подразумевает последующее сложение результата
Почему подразумевает?
Подскажите пожалуйста, если формула расчета кол-ва итераций для алгоритма сортировки равна - n*(n/10) то какая здесь сложность получается?
O(n) или O(n^2) ? Должен ли я отбросить n/10 так как это "n" становится в 10 раз меньше другого n. Или правильней будет отбросить знаменатель 10, тогда получится, что у нас остается n^2.
Как правильно? Я не понимаю... Если ответите, сразу поясните пожалуйста, почему должен быть именно такой ответ.
Или в видео неточность? Может правильное сказать, что незначительное n это не то которое более чем в 2 раза больше, а то которое меньше на степень другого n?
Добрый день! Здесь сложность N^2 т.к. мы отбрасываем константы все, а 10 это констатнта. Правило очень простое -- все что константа сразу отбрасывается, а из оставшихся слагаемых выбирается то, у которого выше скорость роста (еще называют порядок). Градация по убыванию: N! -> 2^N -> N^2 -> N * log N -> N -> SQRT(N) -> log N -> 1
@@Cronis Спасибо! Все понятно теперь! А там где N^2 подразумевается число в любой степени? от 2 и выше? Если будет N^2 * N это будет N^3?
@@maksimsergeevich5939 Не за что :) N^2 < N^3 < N^... < N^X чем меньше степень, тем меньше скорость роста т.е. N^2 + N^3 = O(N^3)
не понял почему на 8:08 функция рекурсивная и почему выполняться будет 10 или 100 раз. там просто линейное вычисление!
При n равном 10 она будет выполняться 10 раз, а при n равном 100 - 100 раз. Все верно.
Это и есть линейная сложность. Не совсем понимаю ваш вопрос.
@@Cronis спасибо, разобрался. там метод вызывает сам себя. и делает это несколько раз. это не относится к интерфейсу Iterable, но принцип тот же по коду
Дополню. Big O от слова Порядок (Ordnung)
Спасибо за видео!
Лучший!
17:17 смущает запись "сколько раз умножить 1 на 2 чтобы получить 16?" сколько раз не умножай 1 на 2 , 16 не получишь ...
имеется в виду в какую степень возвести 2 ж, откуда тут 1
a wakeup call спасибо за вопрос!
Вот пример: 1 * 2 * 2 * 2 *2 = 16. Сколько раз необходимо умножить единицу на двойку? 4 раза
частично поняла суть, но по сравнению с тем, что я смотрела в инете чтобы понять данную тему - это лучшее
Спасибо!
Почему в разборе первого алгоритма говорится, что функция вызывается n раз, ведь нет присваивания n:=n-1?
Подскажите, на какой минуте разбирается алгоритм?
Поправьте, если ошибся. На 9.30 у рекурсивной функции сложность О(1), пожалуй не соглашусь. Попробуйте выполнить эту функцию с х=50, там скорее квадратичная зависимость О(n2). И ещё интересен случай, если подать на вход 0)
Тело функции выполняется за O(1) т.к. не зависит от N. Но выполнятся это самое тело N раз. Поэтому сложность итоговая равна O(N)
Хорошо рассказываете
спасибо, хорошее видео, лайк!
6:34 что такое "О" и "(n)".
Спасибо, хорошее видео
Видео отличное. Правда бинарный поиск можно было нагляднее показать графически: отрезками, деревом или еще как то
Насколько я понял в примере 3 - нужно учитывать дополнительно 4 наружных цикла, если бы он был заполнен кодом. Тогда было бы 16 + 4. O(N² + √N) - так можно было бы записать, если наружный for тоже вызывал бы метод foo()? И по моему sortString сортирует не строки а массивы char в строках? Просто фразу не понял.
Не понял вопрос. В третьем примере сложность O(N^2) т.к. foo выполнится N + (N-1) + (N-2) + ... + 2 + 1 = N(N+1)/N = O(N^2) раз. Это арифметическая прогрессия
Время на видео 22:05 разве не A^2 * B? Там же 3 цикла. И 2 из их - одинаковые (они и будут A^2). А 3-й будет B. Не так?
Добрый день, Ерванд! Первый цикл выполняется А раз, вложенный в него -- В раз, а вложенный в него -- 100000 раз. Итого получаем: A * B * 100000 = O(A * B)
Курс на юдеми не бесплатный сейчас?
Добрый день, курс на udemy сейчас со скидкой 88%
@@Cronis какой курс, дайте ссылку
@@vip51000 держите www.udemy.com/course/big-o-ru/?referralCode=BC5F6819EE463A685AE3
@@Cronis спасибо
Здравствуйте, Немного непонятноm почему O(N² + N) будет равен O(N²), разве не O(N³) должно получиться? Это же базовое сложение, и пренебрегать этим - уже нарушение всей логики
Вы перепутали умножение со сложением:
N*N^2 = N^3
На самом деле log2N это будет когда мы будем точно делить список(массив) попалам на каждой итерации но мы можем же делить на 3, 4 и тд частей и уже не получится логарифм с основанием 2 поэтому в видео есть неточности. Основа логарифма отбрасывается не из-за того что это константа а из-за того что деление списка может быть больше чем на 2 части
Спасибо за комментарий! Основание логарифма это константа. Доказательство это свойство 13: 2.bp.blogspot.com/-RFm5xlyqFf0/WuBL2YudoEI/AAAAAAAAByk/tRjvR5l7FvkB_ylwBEPEh_8x63UTxW8kwCLcBGAs/s1600/009.jpg
По поводу как он образуется: именно деление объекта пополам дает основание 2. Если бы вы делил на части 25% и 75%, было бы основание 4/3. Что тоже константа
@@Cronis ок
@@ruslanvolovik2745
а как с гонором ты начал. и тут де в лужу сел. неуч😂
@@manOfPlanetEarth неуч то ты, я смотрел этот весь бред по сложность алгоритмов и подобную пургу только ради интереса, не более. Я понял, что все это бесполезные вещи, потому что у меня есть друг с которым каждый день общаюсь, он недавно закончил стажировку в гугле, сам сказал что пободные хрени не пригодились в самом гугле, что его очень сильно удивило. Учи дальше этот бред никому не нужный (деньги оно тебе не принесет, баран)😱
@@ruslanvolovik2745
ты в москве сейчас?
int sum(int n) {
if (n == 1) return 1;
return n + sum (n - 1);
}
Выдает ошибку, почему?
File "", line 1
int sum(int n) {
^
SyntaxError: invalid syntax
Это же не питон :)
Здорово, спасибо.
Очень круто
11:06, мне кажется, что сколько раз 1 на 2 не умножай, всегда 2 выходит.
1*2*2*2*2 мы умножили единицу на два 4 раза :)
@@Cronis мы умножили 1 на 2 один раз, потом умножили 2 на 2 один раз, потом 4 на 2 и 8 на 2 по разу
Огромное спасибо, очень последовательно и понятно.
Был рад помочь!
Мне кажется, было бы попроще начать не сразу с концепции bigO, а с математической основы smallO и bigO как верхнего и нижнего пределов ряда. Тогда не пришлось бы оправдываться словами в стиле «что такое О? Это условное обозначение концепции bigO”, которое снимает очевидный вопрос, но порождает следующий - «а почему большое О, что, есть маленькая О?». Концепция пришла из матанализа, так и стоило для порядка к нему обратиться, хотя бы в базовой форме
Под видео есть ссылка на мой полный курс по оценке сложности со всеми математическими выкладками, теорией множеств и всем, всем, всем.
Здесь видео для широкой публики, поэтому такой язык.
Если хотите серьезно изучить - посмотрите курс, вопросов не останется :)
13:51 такая функция называется показательная
Подскажите правильно ли я оценил сложность алгоритма gist.github.com/xfg/3f91181e14c20239affefc218d430edf ? Здесь рекурсия в цикле, которая перебирает объект, в который могут быть вложены другие объекты. У меня получилась сложность O(N * A) насколько я понимаю, это хуже, чем O(N) но всё еще намного лучше, чем O(N * N)
При наличии цикла сложность будет описываться как O(A^N) из-за дерева рекурсивных вызовов
@@Cronis спасибо.
Хочу поставить 10 тысяч лайков автору
Расскажите о канале друзьям, это будет реальная польза мне)
Отличное видео. Спасибо большое!
Видео классное, правда не понятна фраза (17:02) "Сколько раз нужно умножить один на два, что бы получить 16?"
Спасибо за просмотр! Фраза означает: 1 * 2 * 2 * 2 * 2 = 16 то есть мы должны 4 раза умножить 1 на 2 чтобы получить 16
Не корректно так говорить, т.к. сколько бы мы раз не умножали 1 на 2 результат всегда будет 2. Правельно вопрос будет звучать так: в какую степень нужно возвести 2, чтобы получить 16
"ПравЕльно будет ..."))))))
Та, да...
Скажите пож-та на позицию джуна тоже любят спрашивать такие вопросы? Не имею в виду серьезные компании типа google, а компании среднего уровня. что еще любят спрашивать по алгоритмам - так понял поиск в массиве и бинарный поиск?
Вряд ли алгоритмы вообще спрашивают на эту позицию. Для тех кто начинает надо знать хотя бы язык и иметь здравый смысл в суждениях
@@Cronis ну хорошо. а вот допустим про коллекции точно спросят. а потом вопрос - почему одни быстрее других. Или такой вопрос задать - какая оценка временной сложности выборки элемента из HashMap?
Или же у джунов такое обычно не спрашивают? Заранее спасибо за ответ
Все что вы написали - это знание языка.
Сложность из хеш-таблицы O(1) так как за ней стоит по-сути массив. А он работает именно за эту сложность.
ну окей мы имеем O (L * N * (logL + logN)) - это сильно плохо? какие рекомендации, как избегать сложности алгоритма, кроме того, что быть внимательным к вложенным циклам?
Быть внимательным. Если бы была формула идеального кода, его бы писали роботы, и программисты были бы не нужны :)
Дякую, годно!
Пожалуйста
18:04 > автор не знает математику: "Log N" это и означает что логарифм по основанию 2. 2 - это основание логарифма и в данном примере "является константой которую можно выбросить" это просто не имеет смысла.
Само основание важно ибо если оно меньше 1 то ф-я убывающая
в записи bigO опускается 2 но оно всегда подразумевается
7ое свойство логарифма посмотрите :)
@@Cronis там вывод степени из под логарифма, а не основания (при условии что смотрим в один и тот же источник)
Почему пример со сложностью О(А*В) не является О(n^2) ?
Raimbek Toleugaziev т.к. это разные переменные
Спасибо
Сколько раз нужно умножить 1 на 2 что бы получить 16 ? Если только умножать то в результате всегда будет 2.
Спасибо за просмотр! Фраза означает: 1 * 2 * 2 * 2 * 2 = 16 то есть мы должны 4 раза умножить 1 на 2 чтобы получить 16
Курсы Cronis, спасибо за ответ! Хорошо обьясняете не усложняя простые вещи, цветовая гамма видео хорошо подобрана, приятно смотреть не напрягает.