Оценка сложности алгоритма. Сложность алгоритмов. Big O, Большое О
Переглядів 272,101
6 років томуПолный видео-курс со скидкой 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 9 місяців тому
Это материал по книге для подготовки к интервью CRACKING CODING INTERVIEW 189 PROGRAMMING Questions & SOLUTIONS
@Cronis 9 місяців тому
Читайте описание видео)
@fusome 4 роки тому
спасибо, человеческим языком и доходчиво. Наконец-то кто-то это сделал
@xelaksal6690 6 років тому
Огромное спасибо, всё ПРЕДЕЛЬНО понятно!
@Cronis 6 років тому
Спасибо! :)
@FrauKonig 5 років тому
Спасибо огромное за видео ! Все так понятно, особенно на конкретных примерах 💙
@Cronis 5 років тому
Спасибо за комментарий!
@ua_dimka 5 років тому
Очень редко оставляю коментарии, но тут все заслужено. Пожалуй, лучшее объяснение, что я встречал.
@user-ci4zy4tm2b 5 років тому
Круто, очень живо и ясно. Огромное спасибо!
@user-ws2bf2lx5o 4 роки тому
Спасибо, все лаконично, кратко и понятно!
@michaeltes8864 4 роки тому
Очень понятно и доступно, все разложено по полочкам. Хотя и понятно, что это лишь вершина айсберга. Огромное спасибо автору!!!
@user-le3xt6iv4f 4 роки тому
Спасибо за такие простые обьяснения, подписка!
@oleglivcha5041 3 роки тому
Спасибо ,очень информативно и доступно!
@user-jr8sz8cf3q 3 роки тому
Очень полезное видео для старта в изучении сложности алгоритмов!
@user-yn2nv2jd4n Рік тому
Отличный и подробный разбор, качественное объяснение материала, спасибо большое
@ebymamky 2 роки тому
Просто супер, спасибо!!! Отдельное спасибо за примеры
@Cronis 2 роки тому
Всегда рад помочь!
@user-hh4uu9jd9f 5 років тому
Спасибо! отличные примеры из жизни. Очень наглядно! на 13:57 нагляднее пожалуй сравнивать 2^N and N^2. И первый график будет расти быстрее, намного быстрее второго, поэтому второй можно отбросить.
@xrilicc1154 2 роки тому
Отличное объяснение. Спасибо огромное!
@MrCoolDolphin 5 років тому
Офигенное видео!!! Большое спасибо автору!
@dmitry4638 3 роки тому
Отличное разъяснение, спасибо!
@sergeyspitsyn3220 3 роки тому
Количество тактов процессора не равно количеству шагов для выполнения алгоритма. Ибо количество тактов зависит от количества и типов машинных кодов, а компиляция одного и того же алгоритма разными компиляторами или для разных процессоров будет давать разный набор машинных кодов.
@Cronis 3 роки тому
Сергей, вы абсолютно правы. К сожалению сделали ошибку при записи :(
@yessenzhol8989 4 роки тому
спасибо огромное. с твоей подсказкой понял что прежде чем читать кнута и/или кормена надо учить Big O
@PaladinProg 5 років тому
Спасибо большое, теперь стало понятнее
@maksimsergeevich5939 4 роки тому
Спасибо за видео!
@goranlukash1374 Рік тому
Реально спасибо за понятное объяснение....😁
@games4us132 5 років тому
Спасибо, помогли разобраться.
@pgn55555 Рік тому
Спасибо за понятное объяснение!
@sergpoltr2686 6 років тому
Хорошо рассказываете
@C2H5OHH 3 роки тому
Спасибо за урок!
@pansiarhei 5 років тому
Спасибо, хорошее видео
@gofracarton 2 роки тому
Спасибо вам! Проходил курсы от Яндекса по алгоритмам, где объясняли big O, но ничего не понял, а вы очень доходчиво и подробно объяснили. Ещё раз спасибо!
@Cronis 2 роки тому
Рад помочь!
@rodgenk 6 років тому
Здорово, спасибо.
@88billizzard88 3 роки тому
Супер круто, спасибо огромное, очень понятно и информативно, просто бомба
@Cronis 3 роки тому
Спасибо за добрые слова!
@Devivl Рік тому
Спасибо. В общих чертах стало понятно.
@ifdru74 2 роки тому
Большое спасибо за видео. Лично для меня тема стала понятнее.
@Cronis 2 роки тому
Приходите к нам на интенсив, узнаёте ещё больше: ukposts.info/have/v-deo/fpiEaX-ceoJpsIk.html
@vladimirteplov8060 3 роки тому
Отличное видео и курс! Спасибо!
@Cronis 3 роки тому
Рад помочь!
@Alexander-is1eq Рік тому
Полезная информация начинается где то с 6 минуты. Хотел уж было бросить смотреть, но слава богу не бросил. Полезная информация на самом деле полезная. Очень хорошо и понятно все объяснено, спасибо большое.
@Cronis Рік тому
Рад, что досмотрели :)
@bahakulbarakov494 3 роки тому
Сложно очень воспринимать с первого раза XD. С 4 раза понял что да как. Объясняете очень хорошо спасибо за видео.
@vvlkblkc 2 роки тому
Очень хорошее разъяснение - лучшее, что я видел.
@Cronis 2 роки тому
Рад помочь!
@marlonbrando458 4 роки тому
Спасибо, лайк!
@ilyachudakov7944 2 роки тому
Отличное объяснение!
@Alex-zn6vj 2 роки тому
Благодарю! Желаю вам всего самого наилучшего просто вау! ВСЕ ПОНЯТНООО!!!))
@bor3007 4 роки тому
Бро ты крут! Лайк однозначно. Пошел дальше готовиться к собеседованию в фейсбук
@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 на сколько двоек нужно умножить единицу
@nexissis51 5 років тому
Очень хорошее и познавательное видео
@Cronis 5 років тому
Спасибо!
@reddragons9979 5 років тому
Офигенное видео)
@Cronis 5 років тому
Спасибо!
@SuperSonicLeader 3 роки тому
спасибо, хорошее видео, лайк!
@user-ur5kl3mc7j 3 роки тому
Я не очень сведущ в языках но на 19:11 в цикле скобки разные стоят[) потому сложность будет 0. Видос конечно супер щикарный, с примерами, по делу, без тормозов. Респект!
@po1upanow 2 роки тому
Здорово, спасибо
@kirillsushilnikov9614 Рік тому
Спасибо, было познавательно
@yeson6581 2 роки тому
7:06, при передаче на самолёте размер передаваемых файлов не увеличивается, то есть по оси "Количество бит" нет изменения, меняется только время полёта, в зависимости от погодных условий и скорости самолёта. Прямая должна быть вертикальной. Тогда это конечно будет менее наглядно, но оси можно поменять местами и всё будет ok.
@Cronis 2 роки тому
При росте количеств бит время не меняется. График верный
@bor4963 4 роки тому
Хорошо! Нет понятия порядок функции. Тогда легко перейдете от =n к квадрату n
@user-ee1lx1pe7n 3 роки тому
Очень круто
@user-bk1my2xs9j 5 років тому
Поправьте, если ошибся. На 9.30 у рекурсивной функции сложность О(1), пожалуй не соглашусь. Попробуйте выполнить эту функцию с х=50, там скорее квадратичная зависимость О(n2). И ещё интересен случай, если подать на вход 0)
@Cronis 5 років тому
Тело функции выполняется за O(1) т.к. не зависит от N. Но выполнятся это самое тело N раз. Поэтому сложность итоговая равна O(N)
@yakovga 4 роки тому
Спасибо
@dimaspng 10 місяців тому
Спасибо от души!
@Cronis 10 місяців тому
На здоровье)
@awakeupcall5336 4 роки тому
22:58 подскажите, откуда с неба взяли L * log L ?
@Cronis 4 роки тому
В видео говорится, что мы сортируем строки длиной L. В любой сортировке есть всегда код вида if(str1 > str2). А сравнение строк одинаковой длины L -- это сравнение их L символов. Следовательно, мы умножаем сложность сортировки на L
@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 же отбрасывается?
@garikspiridonov3869 4 роки тому
21:13 Квадрат не стал на половину меньше, он стал меньше, приблизительно на одну треть. Хотя согласен с вами, как следует из вашего обьяснения это не важно.
@Cronis 4 роки тому
Вы правы, там не совсем половина, а меньше. Но каквы и сказали, мы игнорируем константы :)
@zion4d Рік тому
пожалуй лучшее! теперь можно приступать к "грокаем алгоритмы"
@Cronis Рік тому
Спасибо! Грокаем алгоритмы -плохая, поверхностная книга, которая путает больше, чем помогает.
@zion4d Рік тому
@@Cronis спасибо! Учту!
@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)
@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
@user-dw4ol9ye7z 2 роки тому
12:43 n< n^2 , n -> inf не тому, що в 2 рази більша друга функція (вона взагалі в n раз більша) , а тому , що похідна другої функції рівна 2n , а першої 1, отже inf > 1, тому і нехтуємо.
@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) раз. Это арифметическая прогрессия
@alionabelomenova1075 4 роки тому
Огромное спасибо, очень последовательно и понятно.
@Cronis 4 роки тому
Был рад помочь!
@iakovryzhichka2832 11 місяців тому
Спасибо за видео! Надеюсь поможет на собеседовании. Может уже спрашивали, но попытаю счастье. Вот не учитываются константы для оценки сложности. Это если у нас бесконечное число операций, то да, но на практике если я пройдусь по конечному массиву за одну секунду, то по идее полмассива я пройду за полсекунды. И если стоит задача оптимизации, то константы тоже важны, верно?
@Cronis 11 місяців тому
Ответ очень очень длинный. Коротко - оценке сложности не показывает точно сложность, а примерную. И на такие мелочи как константы никто не обращает внимание. Под видео есть ссылка на полный курс по оценке сложности, там первые 40 минут подробно рассказывается про константы и как что работает
@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 Ок, понял, тоесть не во всех случаях когда видим вложенный цикл нужно подразумевать перемножение сложностей, как было сказано ранее в видео?
@nikolaysokolov9027 3 роки тому
Отличное видео. Спасибо большое!
@hello_world_zz Рік тому
Препод супер, в стиле Грокаем Алгоритмы
@iforand 3 роки тому
7:28 Как это O(0) означает, что ничего не происходит? O(0) означает, или что для выполнения задачи не требуется выполнять каких либо действий, или что количество операций для выполнения задания уменьшается с ростом сложности задачи асимптотически к нулю. Раньше же сказано, что оценка верхней границы не зависит от времени, а значит говорить, что-то что-то происходит или не происходит не корректно.
@Cronis 3 роки тому
Вы полностью правы. Но как это все сказать для простого человека, который впервые это видит и не напугать его сложными формулировками? :) поэтому вот просто и сказано - суть отражает и не пугает. Под видео есть ссылка на оценку сложности со строгой математикой и с теорией множеств на 2.5 часа. Там мы рассказываем уже все четко для тех, кому нужна математическая строгость. А здесь для широкого зрителя :)
@awakeupcall5336 4 роки тому
ну окей мы имеем O (L * N * (logL + logN)) - это сильно плохо? какие рекомендации, как избегать сложности алгоритма, кроме того, что быть внимательным к вложенным циклам?
@Cronis 4 роки тому
Быть внимательным. Если бы была формула идеального кода, его бы писали роботы, и программисты были бы не нужны :)
@superninja2749 2 роки тому
Здравствуйте, почему 16:20 говорится, что мы должны искать число сначала в 16 элементах, если мы уже делим его на два? то есть, мы ищем в 8 элементах, немного не понял момент.
@Cronis 2 роки тому
Сначала в массиве 16 элементов, потом 8, потом 4, потом 2, потом 1. Поэтому мы сначала ищем среди 16 элементов
@user-br2yk6dd5n 2 роки тому
А почему на 24:12 сложность сортировки строки log(l) ?
@Cronis 2 роки тому
Сложность написана L * log (L)
@vonarut 5 років тому
Огромное Спасибо! Наконец-то понял что такое big O !!! 2019 !!!
@nano28950 Рік тому
Лучший!
@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 года прошло, а ответ за сутки, респект)
@awakeupcall5336 4 роки тому
17:17 смущает запись "сколько раз умножить 1 на 2 чтобы получить 16?" сколько раз не умножай 1 на 2 , 16 не получишь ... имеется в виду в какую степень возвести 2 ж, откуда тут 1
@Cronis 4 роки тому
a wakeup call спасибо за вопрос! Вот пример: 1 * 2 * 2 * 2 *2 = 16. Сколько раз необходимо умножить единицу на двойку? 4 раза
@sherzod_mamadaliev 5 років тому
Cronis, а продолжение будет или это всё?
@Cronis 5 років тому
В ближайшие 10-14 дней появится видео на 2 часа полностью разбирающее теорию Big O во всех подробностях и самых сложны примерах. Но оно будет платным
@Das.Kleine.Krokodil Рік тому
Видео отличное. Правда бинарный поиск можно было нагляднее показать графически: отрезками, деревом или еще как то
@ruslanvolovik2745 3 роки тому
На самом деле log2N это будет когда мы будем точно делить список(массив) попалам на каждой итерации но мы можем же делить на 3, 4 и тд частей и уже не получится логарифм с основанием 2 поэтому в видео есть неточности. Основа логарифма отбрасывается не из-за того что это константа а из-за того что деление списка может быть больше чем на 2 части
@Cronis 3 роки тому
Спасибо за комментарий! Основание логарифма это константа. Доказательство это свойство 13: 2.bp.blogspot.com/-RFm5xlyqFf0/WuBL2YudoEI/AAAAAAAAByk/tRjvR5l7FvkB_ylwBEPEh_8x63UTxW8kwCLcBGAs/s1600/009.jpg По поводу как он образуется: именно деление объекта пополам дает основание 2. Если бы вы делил на части 25% и 75%, было бы основание 4/3. Что тоже константа
@ruslanvolovik2745 3 роки тому
@@Cronis ок
@manOfPlanetEarth 3 роки тому
@@ruslanvolovik2745 а как с гонором ты начал. и тут де в лужу сел. неуч😂
@ruslanvolovik2745 3 роки тому
@@manOfPlanetEarth неуч то ты, я смотрел этот весь бред по сложность алгоритмов и подобную пургу только ради интереса, не более. Я понял, что все это бесполезные вещи, потому что у меня есть друг с которым каждый день общаюсь, он недавно закончил стажировку в гугле, сам сказал что пободные хрени не пригодились в самом гугле, что его очень сильно удивило. Учи дальше этот бред никому не нужный (деньги оно тебе не принесет, баран)😱
@manOfPlanetEarth 3 роки тому
@@ruslanvolovik2745 ты в москве сейчас?
@Noir_Egoiste Рік тому
Больше спасибо, но ничего не понятно, log N получается в половину меньше чем N и в меньше чем N^2 ?
@user-fy2fc6yq4l 3 роки тому
В современном мире ещё очень важное значение играет возможность распараллелить алгоритм. Но я не встречал, как эта концепция вписывается в концепцию bigO. То есть кроме времени и памяти важно понимать, а возможно ли в принципе распараллелить вычисление или нет. От этого ведь тоже может зависеть оценка времени очень сильно.
@Cronis 3 роки тому
Распараллеливание ни на что не влияет с точки зрения сложности. Представьте, что Вам надо последовательно вывести на экран N = 300 букв. И у вас есть 3 процессора. Да, каждый из них выполнит в 3 раза меньше работы и алгоритм выполнится в 3 раза быстрее. То есть итоговая сложность будет N/3 = O(N). Как видно, сложность алгоритма все равно остается линейной, т.е. прежней. Чтобы бы O(N) превратилось в O(1), вам надо 300 процессов. И это всего лишь для обработки 300 букв. А представьте, что вы работает с десятками тысячи букв или элементов массива. Тогда вам необходимы десятки тысяч машин, чтобы решить задачу. Поэтому нужно смотреть на алгоритм, а не на распараллеливание. Оно улучшает ситуацию, но на какое-то константное значение. А константы в оценке сложности отбрасывается.
@alex_mech Рік тому
Ответчик выше имхо слабо знаком с теорией параллельных вычислений, на это намекает грубое сравнение «в лоб» в стиле «чтобы из О(300) сделать О(1), нужно 300 истинно параллельных исполнителей», хотя это всего лишь один частный случай из множества решений. Теория по распараллеливание вычислений есть, она несложная как со стороны алгоритмов, так и со стороны прикладной математики, порог вхождения не настолько высокий (и связь с bigO там кстати тоже оговаривается)
@raimbektoleugaziev4845 5 років тому
Почему пример со сложностью О(А*В) не является О(n^2) ?
@Cronis 5 років тому
Raimbek Toleugaziev т.к. это разные переменные
@andrewstrelnikov8700 Рік тому
16:59 Сколько раз нужно умножить 1 на 2 чтобы получить 16? В целом ход лекции мне нравится. Но вот бы поправили несколько ошибок...
@Cronis Рік тому
1*2*2*2*2 = 16 сколько раз вы умножили 1 на 2 чтобы получить 16?
@user-ee1lx1pe7n 3 роки тому
Время на видео 22:05 разве не A^2 * B? Там же 3 цикла. И 2 из их - одинаковые (они и будут A^2). А 3-й будет B. Не так?
@Cronis 3 роки тому
Добрый день, Ерванд! Первый цикл выполняется А раз, вложенный в него -- В раз, а вложенный в него -- 100000 раз. Итого получаем: A * B * 100000 = O(A * B)
@31more 5 років тому
Почему в разборе первого алгоритма говорится, что функция вызывается n раз, ведь нет присваивания n:=n-1?
@Cronis 5 років тому
Подскажите, на какой минуте разбирается алгоритм?
@Excalib 4 роки тому
21:01 квадрат не стал на половину меньше, вы пропустили 4 шарика:)
@Cronis 4 роки тому
Спасибо за комментарий! Квадрат стал "примерно" меньше на половину. Идея в том, что нам необходимо аппроксимировать результат (по русски прикинуть на глаз куда примерно стремится сумма)
@xfg9183 4 роки тому
Подскажите правильно ли я оценил сложность алгоритма gist.github.com/xfg/3f91181e14c20239affefc218d430edf ? Здесь рекурсия в цикле, которая перебирает объект, в который могут быть вложены другие объекты. У меня получилась сложность O(N * A) насколько я понимаю, это хуже, чем O(N) но всё еще намного лучше, чем O(N * N)
@Cronis 4 роки тому
При наличии цикла сложность будет описываться как O(A^N) из-за дерева рекурсивных вызовов
@xfg9183 4 роки тому
@@Cronis спасибо.
@user-jf5ix4qw3d 6 років тому
Сколько раз нужно умножить 1 на 2 что бы получить 16 ? Если только умножать то в результате всегда будет 2.
@Cronis 6 років тому
Спасибо за просмотр! Фраза означает: 1 * 2 * 2 * 2 * 2 = 16 то есть мы должны 4 раза умножить 1 на 2 чтобы получить 16
@user-jf5ix4qw3d 6 років тому
Курсы Cronis, спасибо за ответ! Хорошо обьясняете не усложняя простые вещи, цветовая гамма видео хорошо подобрана, приятно смотреть не напрягает.
@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 роки тому
Это же не питон :)
@kirill4531 3 роки тому
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 3 роки тому
1*2*2*2*2 мы умножили 1 на двойку 4 раза
@kirill4531 3 роки тому
@@Cronis это я понял, просто я считаю что формулировка задания некорректная. Сколько раз умножить 1 на 2 И На Результат (или как-то так) будет более правильно. А то сколько раз умножить 1 на 2 подразумевает последующее сложение результата
@Cronis 3 роки тому
Почему подразумевает?
@vsezanyato 3 роки тому
Классно, только где j = i .. n там не половину убрали, а меньше
@user-my9sg8we9h 2 роки тому
Дополню. Big O от слова Порядок (Ordnung)
@macrorus1231 6 років тому
Что за прога для презентации?
@-leonid- 5 років тому
Там просто картинки меняются, наложена аудио дорожка.. в принципе многие программы подойдут.. вот мне например нравится эта - Photodex ProShow Producer
@zukora 2 роки тому
Дякую, годно!
@Cronis 2 роки тому
Пожалуйста
@arslanannaev1292 6 років тому
Видео классное, правда не понятна фраза (17:02) "Сколько раз нужно умножить один на два, что бы получить 16?"
@Cronis 6 років тому
Спасибо за просмотр! Фраза означает: 1 * 2 * 2 * 2 * 2 = 16 то есть мы должны 4 раза умножить 1 на 2 чтобы получить 16
@niko-l- 6 років тому
Не корректно так говорить, т.к. сколько бы мы раз не умножали 1 на 2 результат всегда будет 2. Правельно вопрос будет звучать так: в какую степень нужно возвести 2, чтобы получить 16
@stanislavt5834 5 років тому
"ПравЕльно будет ...")))))) Та, да...
@masterswift9700 4 роки тому
Курс на юдеми не бесплатный сейчас?
@Cronis 4 роки тому
Добрый день, курс на udemy сейчас со скидкой 88%
@vip51000 3 роки тому
@@Cronis какой курс, дайте ссылку
@Cronis 3 роки тому
@@vip51000 держите www.udemy.com/course/big-o-ru/?referralCode=BC5F6819EE463A685AE3
@vip51000 3 роки тому
@@Cronis спасибо
@maryka2038 5 років тому
всё было классно, но последний пример вообще не поняла( тем не менее, это видео гораздо понятнее многих других, спасибо!
@Cronis 5 років тому
Спасибо за комментарий! Суть примера в том, что любая сортировка имеет строку вида if(a > b) делать что-то. Так вот если мы сравниваем строки длиной L, например abc и abd, то if выполнится за L операций, а не за одну. Поэтому сложность сортировки L * N * log N
@maryka2038 5 років тому
@@Cronis начинает проясняться, спасибо!))
@akiiaev 4 роки тому
@@Cronis добрый день, А зачем было вводить новую переменную L, если до этого везде использовалась N в не зависимости от длины исходных массивов? Тогда и запись проще: N^2*logN
@vladimirv.v.5730 3 роки тому
@@akiiaev вероятно потому, что характеристики алгоритмов придумали для того, чтобы их можно было сравнивать между собой :) Скажем, пусть одну и ту же операцию можно выполнить двумя разными алгоритмами, сложностью O(N*L²) и O(N²*L) соответственно. Если длина строки L и количество строк N - это величины одного порядка, тогда это действительно равноценные алгоритмы. Но в жизни, как правило, N>>L, поэтому первый алгоритм предпочтительнее.
@akiiaev 3 роки тому
@@vladimirv.v.5730 хм, спасибо за объяснение))
@user-cy8uj5qk7i 2 роки тому
13:51 такая функция называется показательная
@veronikavashkevich8815 5 років тому
Длиной пишется с одной н (22:49)
Front-end Science із Сергієм Пузанковим
Переглядів 118 тис.
Суспільне Вінниця
Переглядів 680 тис.
Фейгин. Смерть Соловьева, арест Шойгу, где будет наступать Россия, штурм Харькова, США нагнули Китай
В гостях у Гордона
Переглядів 992 тис.
Major Tom Workshop
Переглядів 1,8 млн