Оценка сложности алгоритма. Сложность алгоритмов. Big O, Большое О
Рет қаралды 273,237
7 жыл бұрынПолный видео-курс со скидкой 50%: cronis.by/video-course-sale/
Бесплатное обучение: cronis.by/video-materials/
Промо-код YT_20 на -20% на новый живой онлайн курс: cronis.by/online-cart
Видео-курсы:
➤ Полный курс оценки сложности: www.udemy.com/course/big-o-ru...
➤ Полный курс о двоичных числах: www.udemy.com/course/binary_s...
➤ Полный курс о двоичных деревьях: www.udemy.com/course/cronis_b...
Видео расскажет базовые вещи касающиеся Big O и оценки сложности алгоритмов:
➥ Что такое Big O;
➥ Откуда в алгоритмах берется log N;
➥ Как оценивать алгоритмы;
➥ Решения типовых задач по Big O.
Мы поговорим, что такое оценка сложности алгоритма и сложность алгоритмов, а также расскажем что такое Большое О.
Видео является частью лекции школы Cronis: cron.is
Оглавление:
⌚ 02:27 Big O пример из реального мира
⌚ 03:37 Временная оценка сложности
⌚ 10:30 Отбрасывание констант при оценке сложности
⌚ 14:30 Сложение и умножение сложностей
⌚ 15:38 Время выполнения log N
⌚ 18:40 Примеры оценки сложности
✎ Задачи с Google, Facebook, Yandex: • Google задачи. Задача ...
Отдельные темы с нуля:
➤ Двоичная система: • Двоичная система счисл...
➤ Машина Тьюринга: • Машина Тьюринга. Принц...
➤ Индукция: • Лекция 02. Математичес...
➤ Рекурсия: • Рекурсия. Полная теори...
Подробнее можно прочитать здесь: Cracking the Coding Interview by Gayle Laakmann McDowell
Автор книги выше использует материалы: Steven S. Skiena
The Algorithm Design Manual
В видео использованы примеры из данных книг
Телеграмм: t.me/cronisby
Почта: info@cron.is
#Big_O #logN #Оценка_сложности_алгоритмов #О_Большое #двоичный_поиск #бинарный_поиск
@AlexeyShram 6 жыл бұрын
На 13:50 говорится: "На самом деле степенная функция растет гораздо быстрее N в степени 100. Таким образом ответ будет O(2^n)" Допущена ошибка, т.к N^100 - это и есть степенная функция.
@Cronis 6 жыл бұрын
Спасибо! Оговорился :)
@TheANTIdos 6 жыл бұрын
Правильнее было бы сказать, что можно доказать, что показательная функция на бесконечности растет быстрее степенной, вот и все. А так - да, большое спасибо за видео!
@yarikleto5515 3 жыл бұрын
@@ic6406 да, действительно n^100 растет быстрее (когда n - небольшое число), чем 2^n. А так они очень похожи
@vanjka39 3 жыл бұрын
@@ic6406 если рассмотреть функцию f(x)=2^x/x^10, видно что при x~100 f(x)>1, соответственно, показательная функция растет быстрее при x->inf
@jonyxip 3 жыл бұрын
@@ic6406 любая экспоненциальная функция растет быстрее чем полином.
@user-xd3we2qp4i 5 жыл бұрын
Спасибо, благодаря вашему видео у меня сложилось хоть какое-то понятие о "Big O".
@afriendRU 5 жыл бұрын
Просто бомба! Долго боялся взяться разузнать что такое сложность алгоритмов. Тут всё лаконично и объясняется до самого основания. Большое спасибо)
@lobaevni 5 жыл бұрын
Разбор темы сложности алгоритмов отличный. Супер. Долго не мог разобраться, скитался по интернету, а оказалось есть одно видео, которое за 25 минут излагает максимум полезной информации. Спасибо
@Cronis 5 жыл бұрын
Никита Лобаев, спасибо! Был рад помочь!
@pewpew7937 2 жыл бұрын
Дело говорит, твое видео самое полезное на эту тему во всем интернете. Большое спасибо за твой труд)
@Ana-rv6xm 10 ай бұрын
Это материал по книге для подготовки к интервью CRACKING CODING INTERVIEW 189 PROGRAMMING Questions & SOLUTIONS
@Cronis 10 ай бұрын
Читайте описание видео)
@xelaksal6690 6 жыл бұрын
Огромное спасибо, всё ПРЕДЕЛЬНО понятно!
@Cronis 6 жыл бұрын
Спасибо! :)
@fusome 4 жыл бұрын
спасибо, человеческим языком и доходчиво. Наконец-то кто-то это сделал
5 жыл бұрын
Спасибо огромное за видео ! Все так понятно, особенно на конкретных примерах 💙
@Cronis 5 жыл бұрын
Спасибо за комментарий!
@user-ci4zy4tm2b 5 жыл бұрын
Круто, очень живо и ясно. Огромное спасибо!
@ua_dimka 5 жыл бұрын
Очень редко оставляю коментарии, но тут все заслужено. Пожалуй, лучшее объяснение, что я встречал.
@michaeltes8864 4 жыл бұрын
Очень понятно и доступно, все разложено по полочкам. Хотя и понятно, что это лишь вершина айсберга. Огромное спасибо автору!!!
@user-ws2bf2lx5o 4 жыл бұрын
Спасибо, все лаконично, кратко и понятно!
@user-yn2nv2jd4n Жыл бұрын
Отличный и подробный разбор, качественное объяснение материала, спасибо большое
@user-le3xt6iv4f 4 жыл бұрын
Спасибо за такие простые обьяснения, подписка!
@sergeyspitsyn3220 3 жыл бұрын
Количество тактов процессора не равно количеству шагов для выполнения алгоритма. Ибо количество тактов зависит от количества и типов машинных кодов, а компиляция одного и того же алгоритма разными компиляторами или для разных процессоров будет давать разный набор машинных кодов.
@Cronis 3 жыл бұрын
Сергей, вы абсолютно правы. К сожалению сделали ошибку при записи :(
@user-jr8sz8cf3q 3 жыл бұрын
Очень полезное видео для старта в изучении сложности алгоритмов!
@ebymamky 2 жыл бұрын
Просто супер, спасибо!!! Отдельное спасибо за примеры
@Cronis 2 жыл бұрын
Всегда рад помочь!
@oleglivcha5041 3 жыл бұрын
Спасибо ,очень информативно и доступно!
@xrilicc1154 2 жыл бұрын
Отличное объяснение. Спасибо огромное!
@dmitry4638 3 жыл бұрын
Отличное разъяснение, спасибо!
@MrCoolDolphin 5 жыл бұрын
Офигенное видео!!! Большое спасибо автору!
@goranlukash1374 Жыл бұрын
Реально спасибо за понятное объяснение....😁
@Devivl Жыл бұрын
Спасибо. В общих чертах стало понятно.
@pgn55555 Жыл бұрын
Спасибо за понятное объяснение!
@Alex-zn6vj 2 жыл бұрын
Благодарю! Желаю вам всего самого наилучшего просто вау! ВСЕ ПОНЯТНООО!!!))
@PaladinProg 5 жыл бұрын
Спасибо большое, теперь стало понятнее
@vladimirteplov8060 3 жыл бұрын
Отличное видео и курс! Спасибо!
@Cronis 3 жыл бұрын
Рад помочь!
@user-hh4uu9jd9f 5 жыл бұрын
Спасибо! отличные примеры из жизни. Очень наглядно! на 13:57 нагляднее пожалуй сравнивать 2^N and N^2. И первый график будет расти быстрее, намного быстрее второго, поэтому второй можно отбросить.
@yessenzhol8989 4 жыл бұрын
спасибо огромное. с твоей подсказкой понял что прежде чем читать кнута и/или кормена надо учить Big O
@games4us132 5 жыл бұрын
Спасибо, помогли разобраться.
@ifdru74 2 жыл бұрын
Большое спасибо за видео. Лично для меня тема стала понятнее.
@Cronis 2 жыл бұрын
Приходите к нам на интенсив, узнаёте ещё больше: kzfaq.info/get/bejne/fM6DaKyWqLKcf4k.html
@88billizzard88 3 жыл бұрын
Супер круто, спасибо огромное, очень понятно и информативно, просто бомба
@Cronis 3 жыл бұрын
Спасибо за добрые слова!
@bor3007 4 жыл бұрын
Бро ты крут! Лайк однозначно. Пошел дальше готовиться к собеседованию в фейсбук
@vvlkblkc 2 жыл бұрын
Очень хорошее разъяснение - лучшее, что я видел.
@Cronis 2 жыл бұрын
Рад помочь!
@ilyachudakov7944 2 жыл бұрын
Отличное объяснение!
@Alexander-is1eq 2 жыл бұрын
Полезная информация начинается где то с 6 минуты. Хотел уж было бросить смотреть, но слава богу не бросил. Полезная информация на самом деле полезная. Очень хорошо и понятно все объяснено, спасибо большое.
@Cronis 2 жыл бұрын
Рад, что досмотрели :)
@C2H5OHH 3 жыл бұрын
Спасибо за урок!
@gofracarton 2 жыл бұрын
Спасибо вам! Проходил курсы от Яндекса по алгоритмам, где объясняли big O, но ничего не понял, а вы очень доходчиво и подробно объяснили. Ещё раз спасибо!
@Cronis 2 жыл бұрын
Рад помочь!
@bahakulbarakov494 3 жыл бұрын
Сложно очень воспринимать с первого раза XD. С 4 раза понял что да как. Объясняете очень хорошо спасибо за видео.
@sergpoltr2686 6 жыл бұрын
Хорошо рассказываете
@maksimsergeevich5939 4 жыл бұрын
Спасибо за видео!
@rodgenk 6 жыл бұрын
Здорово, спасибо.
@kirillsushilnikov9614 Жыл бұрын
Спасибо, было познавательно
@pansiarhei 5 жыл бұрын
Спасибо, хорошее видео
@nexissis51 5 жыл бұрын
Очень хорошее и познавательное видео
@Cronis 5 жыл бұрын
Спасибо!
@marlonbrando458 4 жыл бұрын
Спасибо, лайк!
@user-ur5kl3mc7j 3 жыл бұрын
Я не очень сведущ в языках но на 19:11 в цикле скобки разные стоят[) потому сложность будет 0. Видос конечно супер щикарный, с примерами, по делу, без тормозов. Респект!
@awakeupcall5336 4 жыл бұрын
22:58 подскажите, откуда с неба взяли L * log L ?
@Cronis 4 жыл бұрын
В видео говорится, что мы сортируем строки длиной L. В любой сортировке есть всегда код вида if(str1 > str2). А сравнение строк одинаковой длины L -- это сравнение их L символов. Следовательно, мы умножаем сложность сортировки на L
@SuperSonicLeader 3 жыл бұрын
спасибо, хорошее видео, лайк!
@po1upanow 2 жыл бұрын
Здорово, спасибо
@user-my9sg8we9h 2 жыл бұрын
Дополню. Big O от слова Порядок (Ordnung)
@cracoh 4 жыл бұрын
Спасибо зо подробное и доходчивое объяснение ключевых базовых понятий. 25 минут видео я посмотрел за час - прорешивал, записывал. Не знаю было ли где-то в комментах, но меня покоробила фраза на 17.11 - "сколько раз нужно умножить 1 на 2 чтобы получить 16?" мой ответ 8. потому как 1*2+1*2+1*2+1*2=8 а не 4. Но, в общем понятно что имелось в виду.
@Roomaa111 2 жыл бұрын
1*2*2*2*2=16
@cracoh 2 жыл бұрын
@@Roomaa111 хех, класс!
@andrusia2048 2 жыл бұрын
@@Roomaa111 на сколько двоек нужно умножить единицу
@maksimsergeevich5939 4 жыл бұрын
Подскажите пожалуйста, если формула расчета кол-ва итераций для алгоритма сортировки равна - n*(n/10) то какая здесь сложность получается? O(n) или O(n^2) ? Должен ли я отбросить n/10 так как это "n" становится в 10 раз меньше другого n. Или правильней будет отбросить знаменатель 10, тогда получится, что у нас остается n^2. Как правильно? Я не понимаю... Если ответите, сразу поясните пожалуйста, почему должен быть именно такой ответ. Или в видео неточность? Может правильное сказать, что незначительное n это не то которое более чем в 2 раза больше, а то которое меньше на степень другого n?
@Cronis 4 жыл бұрын
Добрый день! Здесь сложность N^2 т.к. мы отбрасываем константы все, а 10 это констатнта. Правило очень простое -- все что константа сразу отбрасывается, а из оставшихся слагаемых выбирается то, у которого выше скорость роста (еще называют порядок). Градация по убыванию: N! -> 2^N -> N^2 -> N * log N -> N -> SQRT(N) -> log N -> 1
@maksimsergeevich5939 4 жыл бұрын
@@Cronis Спасибо! Все понятно теперь! А там где N^2 подразумевается число в любой степени? от 2 и выше? Если будет N^2 * N это будет N^3?
@Cronis 4 жыл бұрын
@@maksimsergeevich5939 Не за что :) N^2 < N^3 < N^... < N^X чем меньше степень, тем меньше скорость роста т.е. N^2 + N^3 = O(N^3)
@reddragons9979 5 жыл бұрын
Офигенное видео)
@Cronis 5 жыл бұрын
Спасибо!
@user-my9ux9mb1m 5 жыл бұрын
В 12:46 говорится, что N^2 больше в два раза чем N. Но это бред! В два раза больше - это 2*N, а N^2 - это больше N в N раз. Да и в целом, учитывая оговорки и некорректные высказывания, указанные ниже в комментариях, можно сделать вывод, что к такому лектору на эти курсы ходить не стоит. Хотя в целом видео заслуживает внимания.
@Cronis 5 жыл бұрын
Андрей Чернов, спасибо за комментарий! Возможно вы не расслышали, что было сказано: эн квадрат __больше__ чем в два раза превышает эн. Поэтому мы говорим, что эн квадрат намного больше эн.
@user-my9ux9mb1m 5 жыл бұрын
Переслушал еще раз. И опять слышу то, что написал выше. Дословно то, что говорится в видео: "Значительно - это значит в два раза. Если эн в два раза больше другого числа эм, значит эн значительно больше чем эм". Я понял, что хотел сказать лектор, но это прозвучало на фоне объяснения почему N^2 значительно больше N. Вот как раз слов "эн квадрат _больше_ чем в два раза превышает эн" сказано не было. Поэтому возникает путаница.
@nalilata 5 жыл бұрын
@@Cronis извините, а зачем нам это "N^2 значительно больше N" если чтобы его отбросить, достаточно того, что N не больше N^2. мы даже строчкой выше N^2 отбросили, к чему такая возня с N, если мы его отбросим, в 2 раза оно меньше N^2 или даже в 1? и дальше 18:28 "или N + log N" - log N же отбрасывается?
@zion4d Жыл бұрын
пожалуй лучшее! теперь можно приступать к "грокаем алгоритмы"
@Cronis Жыл бұрын
Спасибо! Грокаем алгоритмы -плохая, поверхностная книга, которая путает больше, чем помогает.
@zion4d Жыл бұрын
@@Cronis спасибо! Учту!
@dimaspng Жыл бұрын
Спасибо от души!
@Cronis Жыл бұрын
На здоровье)
@garikspiridonov3869 4 жыл бұрын
21:13 Квадрат не стал на половину меньше, он стал меньше, приблизительно на одну треть. Хотя согласен с вами, как следует из вашего обьяснения это не важно.
@Cronis 4 жыл бұрын
Вы правы, там не совсем половина, а меньше. Но каквы и сказали, мы игнорируем константы :)
@user-ee1lx1pe7n 3 жыл бұрын
Очень круто
@yakovga 4 жыл бұрын
Спасибо
@alexzhyshko9762 5 жыл бұрын
В примере 3 было сказано, что сложность алгоритма N^2, но если посмотреть внимательнее, то N(N-1)(N-2)...1 это Nфакториал. Тоесть будет О(N!). И если смотреть по квадрату 4х4,то отсекается не половина, а немного меньше половины, что, логично предположить, будет О(nlogn). И если расписывать эти два случая, то мы получим равенство сложностей N! =~ NLogN. Если в чем-то не прав, то поправьте пожалуйста
@Cronis 5 жыл бұрын
будет: N + (N - 1) + (N - 2) .... + 3 + 2 + 1 = N(N+1)/2 = O(N^2) В треугольнике тоже кружки идут как 4 + 3 + 2 + 1 = 4*(4+1)/2 = 10
@hello_world_zz Жыл бұрын
Препод супер, в стиле Грокаем Алгоритмы
@bor4963 4 жыл бұрын
Хорошо! Нет понятия порядок функции. Тогда легко перейдете от =n к квадрату n
@vonarut 5 жыл бұрын
Огромное Спасибо! Наконец-то понял что такое big O !!! 2019 !!!
@nikolaysokolov9027 4 жыл бұрын
Отличное видео. Спасибо большое!
@yeson6581 2 жыл бұрын
7:06, при передаче на самолёте размер передаваемых файлов не увеличивается, то есть по оси "Количество бит" нет изменения, меняется только время полёта, в зависимости от погодных условий и скорости самолёта. Прямая должна быть вертикальной. Тогда это конечно будет менее наглядно, но оси можно поменять местами и всё будет ok.
@Cronis 2 жыл бұрын
При росте количеств бит время не меняется. График верный
@turbojonah2881 4 жыл бұрын
Здравствуйте, спасибо за видео! Есть один вопрос. На 20:05 вы говорите, что сложность алгоритма будет ровна О(N+(N-1)+(N-2)+...+2+1). Не совсем понятно почему вы складываете кол-во операций, ведь в предыдущем примере с вложенным циклом, сложность алгоритма ровнялась О(N*N). Разве тут не должно было получится, что сложность алгоритма ровняется О(N*N+N(N-1)+N(N-2)+...+2N+N?
@Cronis 4 жыл бұрын
Добрый день! Смотрите: в первом цикле i = 0, то есть второй цикл идёт от j = 0 до N. Затем i = 1 то есть второй цикл идёт от j = 1 до N затем второй цикл идёт от j = 2 до N. Следуя этой логике, получаем N+(N-1)+(N-2)+...+2+1
@user-dt8vj3cv4e 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 3 жыл бұрын
@@Cronis тут вы не правы, из N+(N-1)+(N-2)+...+2+1 никак не вывести N^2, следовательно, как и писали выше правильная запись будет вида N*(N+(N-1)+(N-2)+...+2+1)
@Cronis 3 жыл бұрын
@@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 3 жыл бұрын
@@Cronis Ок, понял, тоесть не во всех случаях когда видим вложенный цикл нужно подразумевать перемножение сложностей, как было сказано ранее в видео?
@xfg9183 4 жыл бұрын
Подскажите правильно ли я оценил сложность алгоритма gist.github.com/xfg/3f91181e14c20239affefc218d430edf ? Здесь рекурсия в цикле, которая перебирает объект, в который могут быть вложены другие объекты. У меня получилась сложность O(N * A) насколько я понимаю, это хуже, чем O(N) но всё еще намного лучше, чем O(N * N)
@Cronis 4 жыл бұрын
При наличии цикла сложность будет описываться как O(A^N) из-за дерева рекурсивных вызовов
@xfg9183 4 жыл бұрын
@@Cronis спасибо.
@nano28950 Жыл бұрын
Лучший!
@superninja2749 2 жыл бұрын
Здравствуйте, почему 16:20 говорится, что мы должны искать число сначала в 16 элементах, если мы уже делим его на два? то есть, мы ищем в 8 элементах, немного не понял момент.
@Cronis 2 жыл бұрын
Сначала в массиве 16 элементов, потом 8, потом 4, потом 2, потом 1. Поэтому мы сначала ищем среди 16 элементов
@user-bk1my2xs9j 5 жыл бұрын
Поправьте, если ошибся. На 9.30 у рекурсивной функции сложность О(1), пожалуй не соглашусь. Попробуйте выполнить эту функцию с х=50, там скорее квадратичная зависимость О(n2). И ещё интересен случай, если подать на вход 0)
@Cronis 5 жыл бұрын
Тело функции выполняется за O(1) т.к. не зависит от N. Но выполнятся это самое тело N раз. Поэтому сложность итоговая равна O(N)
@iakovryzhichka2832 Жыл бұрын
Спасибо за видео! Надеюсь поможет на собеседовании. Может уже спрашивали, но попытаю счастье. Вот не учитываются константы для оценки сложности. Это если у нас бесконечное число операций, то да, но на практике если я пройдусь по конечному массиву за одну секунду, то по идее полмассива я пройду за полсекунды. И если стоит задача оптимизации, то константы тоже важны, верно?
@Cronis Жыл бұрын
Ответ очень очень длинный. Коротко - оценке сложности не показывает точно сложность, а примерную. И на такие мелочи как константы никто не обращает внимание. Под видео есть ссылка на полный курс по оценке сложности, там первые 40 минут подробно рассказывается про константы и как что работает
@31more 5 жыл бұрын
Почему в разборе первого алгоритма говорится, что функция вызывается n раз, ведь нет присваивания n:=n-1?
@Cronis 5 жыл бұрын
Подскажите, на какой минуте разбирается алгоритм?
@alionabelomenova1075 4 жыл бұрын
Огромное спасибо, очень последовательно и понятно.
@Cronis 4 жыл бұрын
Был рад помочь!
@awakeupcall5336 4 жыл бұрын
ну окей мы имеем O (L * N * (logL + logN)) - это сильно плохо? какие рекомендации, как избегать сложности алгоритма, кроме того, что быть внимательным к вложенным циклам?
@Cronis 4 жыл бұрын
Быть внимательным. Если бы была формула идеального кода, его бы писали роботы, и программисты были бы не нужны :)
@shurale85 2 жыл бұрын
Скажите, пожалуйста, а почему сортировка строки L*Log_L?
@Cronis 2 жыл бұрын
Встроеннная в язык сортировка это сонтировка quicksort. Ей мы и сортируем строки. И ее сложность O(L * logL)
@pinkierar_real 8 ай бұрын
@@Cronis это бы совершенно неочевидно)
@Noir_Egoiste Жыл бұрын
Больше спасибо, но ничего не понятно, log N получается в половину меньше чем N и в меньше чем N^2 ?
@taboollive727 3 жыл бұрын
Насколько я понял в примере 3 - нужно учитывать дополнительно 4 наружных цикла, если бы он был заполнен кодом. Тогда было бы 16 + 4. O(N² + √N) - так можно было бы записать, если наружный for тоже вызывал бы метод foo()? И по моему sortString сортирует не строки а массивы char в строках? Просто фразу не понял.
@Cronis 3 жыл бұрын
Не понял вопрос. В третьем примере сложность O(N^2) т.к. foo выполнится N + (N-1) + (N-2) + ... + 2 + 1 = N(N+1)/N = O(N^2) раз. Это арифметическая прогрессия
@user-br2yk6dd5n 2 жыл бұрын
А почему на 24:12 сложность сортировки строки log(l) ?
@Cronis 2 жыл бұрын
Сложность написана L * log (L)
@Das.Kleine.Krokodil Жыл бұрын
Видео отличное. Правда бинарный поиск можно было нагляднее показать графически: отрезками, деревом или еще как то
@awakeupcall5336 4 жыл бұрын
17:17 смущает запись "сколько раз умножить 1 на 2 чтобы получить 16?" сколько раз не умножай 1 на 2 , 16 не получишь ... имеется в виду в какую степень возвести 2 ж, откуда тут 1
@Cronis 4 жыл бұрын
a wakeup call спасибо за вопрос! Вот пример: 1 * 2 * 2 * 2 *2 = 16. Сколько раз необходимо умножить единицу на двойку? 4 раза
@olegchumin6634 Жыл бұрын
Лучшее объяснение, что видел вообще.
@andrewstrelnikov8700 Жыл бұрын
16:59 Сколько раз нужно умножить 1 на 2 чтобы получить 16? В целом ход лекции мне нравится. Но вот бы поправили несколько ошибок...
@Cronis Жыл бұрын
1*2*2*2*2 = 16 сколько раз вы умножили 1 на 2 чтобы получить 16?
@johnwhite9906 2 жыл бұрын
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 2 жыл бұрын
Это же не питон :)
@iforand 3 жыл бұрын
7:28 Как это O(0) означает, что ничего не происходит? O(0) означает, или что для выполнения задачи не требуется выполнять каких либо действий, или что количество операций для выполнения задания уменьшается с ростом сложности задачи асимптотически к нулю. Раньше же сказано, что оценка верхней границы не зависит от времени, а значит говорить, что-то что-то происходит или не происходит не корректно.
@Cronis 3 жыл бұрын
Вы полностью правы. Но как это все сказать для простого человека, который впервые это видит и не напугать его сложными формулировками? :) поэтому вот просто и сказано - суть отражает и не пугает. Под видео есть ссылка на оценку сложности со строгой математикой и с теорией множеств на 2.5 часа. Там мы рассказываем уже все четко для тех, кому нужна математическая строгость. А здесь для широкого зрителя :)
@user-jf5ix4qw3d 6 жыл бұрын
Сколько раз нужно умножить 1 на 2 что бы получить 16 ? Если только умножать то в результате всегда будет 2.
@Cronis 6 жыл бұрын
Спасибо за просмотр! Фраза означает: 1 * 2 * 2 * 2 * 2 = 16 то есть мы должны 4 раза умножить 1 на 2 чтобы получить 16
@user-jf5ix4qw3d 6 жыл бұрын
Курсы Cronis, спасибо за ответ! Хорошо обьясняете не усложняя простые вещи, цветовая гамма видео хорошо подобрана, приятно смотреть не напрягает.
@macrorus1231 6 жыл бұрын
Что за прога для презентации?
@-leonid- 5 жыл бұрын
Там просто картинки меняются, наложена аудио дорожка.. в принципе многие программы подойдут.. вот мне например нравится эта - Photodex ProShow Producer
@sherzod_mamadaliev 5 жыл бұрын
Cronis, а продолжение будет или это всё?
@Cronis 5 жыл бұрын
В ближайшие 10-14 дней появится видео на 2 часа полностью разбирающее теорию Big O во всех подробностях и самых сложны примерах. Но оно будет платным
@nighthoves7212 4 жыл бұрын
частично поняла суть, но по сравнению с тем, что я смотрела в инете чтобы понять данную тему - это лучшее
@Cronis 4 жыл бұрын
Спасибо!
@mindwin7158 2 жыл бұрын
Ведёт к серьезной потерЕ
@korsman723 Жыл бұрын
Здравствуйте, Немного непонятноm почему O(N² + N) будет равен O(N²), разве не O(N³) должно получиться? Это же базовое сложение, и пренебрегать этим - уже нарушение всей логики
@Cronis Жыл бұрын
Вы перепутали умножение со сложением: N*N^2 = N^3
@jakepomg317 2 жыл бұрын
Не понятно в 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 2 жыл бұрын
Просто вынесли за скобки N * L. То есть не вашем примере 2 + 2 * 2 = 2 * (1 + 1 * 2)
@jakepomg317 2 жыл бұрын
@@Cronis Спасибо🙏 3 года прошло, а ответ за сутки, респект)
@user-ee1lx1pe7n 3 жыл бұрын
Время на видео 22:05 разве не A^2 * B? Там же 3 цикла. И 2 из их - одинаковые (они и будут A^2). А 3-й будет B. Не так?
@Cronis 3 жыл бұрын
Добрый день, Ерванд! Первый цикл выполняется А раз, вложенный в него -- В раз, а вложенный в него -- 100000 раз. Итого получаем: A * B * 100000 = O(A * B)
@user-dw4ol9ye7z 2 жыл бұрын
12:43 n< n^2 , n -> inf не тому, що в 2 рази більша друга функція (вона взагалі в n раз більша) , а тому , що похідна другої функції рівна 2n , а першої 1, отже inf > 1, тому і нехтуємо.
@raimbektoleugaziev4845 5 жыл бұрын
Почему пример со сложностью О(А*В) не является О(n^2) ?
@Cronis 5 жыл бұрын
Raimbek Toleugaziev т.к. это разные переменные
@ruslanvolovik2745 4 жыл бұрын
На самом деле log2N это будет когда мы будем точно делить список(массив) попалам на каждой итерации но мы можем же делить на 3, 4 и тд частей и уже не получится логарифм с основанием 2 поэтому в видео есть неточности. Основа логарифма отбрасывается не из-за того что это константа а из-за того что деление списка может быть больше чем на 2 части
@Cronis 4 жыл бұрын
Спасибо за комментарий! Основание логарифма это константа. Доказательство это свойство 13: 2.bp.blogspot.com/-RFm5xlyqFf0/WuBL2YudoEI/AAAAAAAAByk/tRjvR5l7FvkB_ylwBEPEh_8x63UTxW8kwCLcBGAs/s1600/009.jpg По поводу как он образуется: именно деление объекта пополам дает основание 2. Если бы вы делил на части 25% и 75%, было бы основание 4/3. Что тоже константа
@ruslanvolovik2745 4 жыл бұрын
@@Cronis ок
@manOfPlanetEarth 3 жыл бұрын
@@ruslanvolovik2745 а как с гонором ты начал. и тут де в лужу сел. неуч😂
@ruslanvolovik2745 3 жыл бұрын
@@manOfPlanetEarth неуч то ты, я смотрел этот весь бред по сложность алгоритмов и подобную пургу только ради интереса, не более. Я понял, что все это бесполезные вещи, потому что у меня есть друг с которым каждый день общаюсь, он недавно закончил стажировку в гугле, сам сказал что пободные хрени не пригодились в самом гугле, что его очень сильно удивило. Учи дальше этот бред никому не нужный (деньги оно тебе не принесет, баран)😱
@manOfPlanetEarth 3 жыл бұрын
@@ruslanvolovik2745 ты в москве сейчас?
@masterswift9700 4 жыл бұрын
Курс на юдеми не бесплатный сейчас?
@Cronis 4 жыл бұрын
Добрый день, курс на udemy сейчас со скидкой 88%
@vip51000 3 жыл бұрын
@@Cronis какой курс, дайте ссылку
@Cronis 3 жыл бұрын
@@vip51000 держите www.udemy.com/course/big-o-ru/?referralCode=BC5F6819EE463A685AE3
@vip51000 3 жыл бұрын
@@Cronis спасибо
@vsezanyato 3 жыл бұрын
Классно, только где j = i .. n там не половину убрали, а меньше
@stockspulse 7 ай бұрын
Хочу поставить 10 тысяч лайков автору
@Cronis 7 ай бұрын
Расскажите о канале друзьям, это будет реальная польза мне)
@Excalib 4 жыл бұрын
21:01 квадрат не стал на половину меньше, вы пропустили 4 шарика:)
@Cronis 4 жыл бұрын
Спасибо за комментарий! Квадрат стал "примерно" меньше на половину. Идея в том, что нам необходимо аппроксимировать результат (по русски прикинуть на глаз куда примерно стремится сумма)
@user-cy8uj5qk7i 2 жыл бұрын
13:51 такая функция называется показательная
Diana Belitskay
Рет қаралды 18 МЛН
Senior Software Vlogger
Рет қаралды 350 М.
Cronis Academy
Рет қаралды 9 М.
Елена Литвинова — Искусство Веб-разработки 🛸
Рет қаралды 28 М.
Фоксфорд
Рет қаралды 64 М.
Diana Belitskay
Рет қаралды 18 МЛН