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

Поділитися
Вставка
  • Опубліковано 23 гру 2024

КОМЕНТАРІ •

  • @AlexeyShram
    @AlexeyShram 7 років тому +122

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

    • @Cronis
      @Cronis  7 років тому +28

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

    • @TheANTIdos
      @TheANTIdos 7 років тому +7

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

    • @yarikleto5515
      @yarikleto5515 4 роки тому

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

    • @vanjka39
      @vanjka39 4 роки тому +3

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

    • @jonyxip
      @jonyxip 3 роки тому +1

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

  • @ВолодимирБарибін-е8у
    @ВолодимирБарибін-е8у 5 років тому +20

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

  • @afriendRU
    @afriendRU 5 років тому +10

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

  • @lobaevni
    @lobaevni 6 років тому +101

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

    • @Cronis
      @Cronis  6 років тому +4

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

    • @pewpew7937
      @pewpew7937 3 роки тому +1

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

    • @Ana-rv6xm
      @Ana-rv6xm Рік тому

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

    • @Cronis
      @Cronis  Рік тому

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

  • @ua_dimka
    @ua_dimka 6 років тому +6

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

  • @michaeltes8864
    @michaeltes8864 4 роки тому +11

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

  • @Alexander-is1eq
    @Alexander-is1eq 2 роки тому

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

    • @Cronis
      @Cronis  2 роки тому

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

  • @sergeyspitsyn3220
    @sergeyspitsyn3220 4 роки тому +15

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

    • @Cronis
      @Cronis  4 роки тому +1

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

  • @fusome
    @fusome 4 роки тому +6

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

  • @xelaksal6690
    @xelaksal6690 7 років тому +11

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

    • @Cronis
      @Cronis  7 років тому +2

      Спасибо! :)

  • @gofracarton
    @gofracarton 2 роки тому

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

    • @Cronis
      @Cronis  2 роки тому +1

      Рад помочь!

  •  5 років тому +8

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

    • @Cronis
      @Cronis  5 років тому +1

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

  • @ebymamky
    @ebymamky 3 роки тому +2

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

    • @Cronis
      @Cronis  3 роки тому +1

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

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

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

  • @vladimirteplov8060
    @vladimirteplov8060 3 роки тому +1

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

    • @Cronis
      @Cronis  3 роки тому

      Рад помочь!

  • @bahakulbarakov494
    @bahakulbarakov494 4 роки тому +2

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

  • @goranlukash1374
    @goranlukash1374 2 роки тому +1

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

  • @vvlkblkc
    @vvlkblkc 3 роки тому

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

    • @Cronis
      @Cronis  3 роки тому

      Рад помочь!

  • @cracoh
    @cracoh 4 роки тому +4

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

    • @Roomaa111
      @Roomaa111 3 роки тому +1

      1*2*2*2*2=16

    • @cracoh
      @cracoh 3 роки тому +1

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

    • @andrusia2048
      @andrusia2048 2 роки тому

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

  • @Devivl
    @Devivl 2 роки тому

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

  • @АлексСапс
    @АлексСапс 6 років тому +3

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

  • @Alex-zn6vj
    @Alex-zn6vj 3 роки тому

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

  • @olegchumin6634
    @olegchumin6634 Рік тому

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

  • @ЕвгенЗадко
    @ЕвгенЗадко 3 роки тому

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

  • @zion4d
    @zion4d 2 роки тому

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

    • @Cronis
      @Cronis  2 роки тому +2

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

    • @zion4d
      @zion4d 2 роки тому

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

  • @yeson6581
    @yeson6581 3 роки тому

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

    • @Cronis
      @Cronis  3 роки тому +2

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

  • @ifdru74
    @ifdru74 3 роки тому

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

    • @Cronis
      @Cronis  3 роки тому +1

      Приходите к нам на интенсив, узнаёте ещё больше: ua-cam.com/video/FhS5IeCL8OU/v-deo.html

  • @ИльяИлья-ф8щ
    @ИльяИлья-ф8щ 4 роки тому

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

  • @Гарри-ю3и
    @Гарри-ю3и 6 років тому +1

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

  • @kirillsushilnikov9614
    @kirillsushilnikov9614 Рік тому

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

  • @awakeupcall5336
    @awakeupcall5336 5 років тому +9

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

    • @Cronis
      @Cronis  5 років тому +3

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

  • @ЕвгенийСедых-и2щ
    @ЕвгенийСедых-и2щ 4 роки тому

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

  • @ОлафШкипер
    @ОлафШкипер 4 роки тому

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

  • @PapaCarlo87
    @PapaCarlo87 4 роки тому

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

  • @bor3007
    @bor3007 4 роки тому

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

  • @TarasMaliarchuk-o4d
    @TarasMaliarchuk-o4d 2 роки тому

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

  • @dimaspng
    @dimaspng Рік тому

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

    • @Cronis
      @Cronis  Рік тому +1

      На здоровье)

  • @garikspiridonov3869
    @garikspiridonov3869 4 роки тому +4

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

    • @Cronis
      @Cronis  4 роки тому

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

  • @andrewstrelnikov8700
    @andrewstrelnikov8700 2 роки тому

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

    • @Cronis
      @Cronis  2 роки тому +1

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

  • @dmitry4638
    @dmitry4638 3 роки тому

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

  • @shurale85
    @shurale85 3 роки тому +1

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

    • @Cronis
      @Cronis  3 роки тому

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

    • @pinkierar_real
      @pinkierar_real Рік тому

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

  • @MrCoolDolphin
    @MrCoolDolphin 6 років тому

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

  • @88billizzard88
    @88billizzard88 4 роки тому

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

    • @Cronis
      @Cronis  4 роки тому +1

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

  • @nexissis51
    @nexissis51 6 років тому

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

    • @Cronis
      @Cronis  6 років тому

      Спасибо!

  • @alexzhyshko9762
    @alexzhyshko9762 5 років тому +2

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

    • @Cronis
      @Cronis  5 років тому +1

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

  • @Математик-л7ы
    @Математик-л7ы 3 роки тому

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

    • @Cronis
      @Cronis  3 роки тому

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

  • @C2H5OHH
    @C2H5OHH 4 роки тому

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

  • @jakepomg317
    @jakepomg317 3 роки тому

    Не понятно в 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
      @Cronis  3 роки тому

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

    • @jakepomg317
      @jakepomg317 3 роки тому

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

  • @iforand
    @iforand 3 роки тому

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

    • @Cronis
      @Cronis  3 роки тому +1

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

  • @iakovryzhichka2832
    @iakovryzhichka2832 Рік тому

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

    • @Cronis
      @Cronis  Рік тому

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

  • @АндрейЧернов-ь2ш
    @АндрейЧернов-ь2ш 6 років тому +23

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

    • @Cronis
      @Cronis  6 років тому +4

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

    • @АндрейЧернов-ь2ш
      @АндрейЧернов-ь2ш 6 років тому +2

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

    • @nalilata
      @nalilata 5 років тому +1

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

  • @superninja2749
    @superninja2749 3 роки тому

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

    • @Cronis
      @Cronis  3 роки тому

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

  • @vonarut
    @vonarut 5 років тому +2

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

  • @turbojonah2881
    @turbojonah2881 4 роки тому +2

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

    • @Cronis
      @Cronis  4 роки тому +1

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

    • @павелшимаров-ц3о
      @павелшимаров-ц3о 4 роки тому

      @@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
      @MrPr0927 4 роки тому

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

    • @Cronis
      @Cronis  4 роки тому

      @@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
      @MrPr0927 4 роки тому +1

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

  • @marlonbrando458
    @marlonbrando458 4 роки тому +1

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

  • @PaladinProg
    @PaladinProg 6 років тому

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

  • @Noir_Egoiste
    @Noir_Egoiste Рік тому

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

  • @bor4963
    @bor4963 5 років тому +1

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

  • @reddragons9979
    @reddragons9979 5 років тому +1

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

    • @Cronis
      @Cronis  5 років тому

      Спасибо!

  • @Евгений-ы4м3ж
    @Евгений-ы4м3ж Місяць тому

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

  • @games4us132
    @games4us132 5 років тому

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

  • @hello_world_zz
    @hello_world_zz 2 роки тому

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

  • @kirill4531
    @kirill4531 4 роки тому

    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
      @Cronis  4 роки тому

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

    • @kirill4531
      @kirill4531 4 роки тому

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

    • @Cronis
      @Cronis  4 роки тому

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

  • @maksimsergeevich5939
    @maksimsergeevich5939 4 роки тому +1

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

    • @Cronis
      @Cronis  4 роки тому +1

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

    • @maksimsergeevich5939
      @maksimsergeevich5939 4 роки тому

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

    • @Cronis
      @Cronis  4 роки тому +1

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

  • @Daoway-f7o
    @Daoway-f7o 2 роки тому

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

    • @Cronis
      @Cronis  2 роки тому

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

    • @Daoway-f7o
      @Daoway-f7o 2 роки тому

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

  • @ИгнатМирзализадэ
    @ИгнатМирзализадэ 2 роки тому +1

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

  • @maksimsergeevich5939
    @maksimsergeevich5939 4 роки тому

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

  • @nano28950
    @nano28950 2 роки тому

    Лучший!

  • @awakeupcall5336
    @awakeupcall5336 5 років тому +2

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

    • @Cronis
      @Cronis  5 років тому

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

  • @nighthoves7212
    @nighthoves7212 4 роки тому +1

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

    • @Cronis
      @Cronis  4 роки тому

      Спасибо!

  • @31more
    @31more 5 років тому +2

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

    • @Cronis
      @Cronis  5 років тому

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

  • @ВадимЛадик-т7м
    @ВадимЛадик-т7м 5 років тому

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

    • @Cronis
      @Cronis  5 років тому

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

  • @sergpoltr2686
    @sergpoltr2686 7 років тому

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

  • @SuperSonicLeader
    @SuperSonicLeader 4 роки тому

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

  • @ФдрФфф
    @ФдрФфф Рік тому

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

  • @pansiarhei
    @pansiarhei 6 років тому +1

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

  • @Das.Kleine.Krokodil
    @Das.Kleine.Krokodil Рік тому

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

  • @taboollive727
    @taboollive727 4 роки тому

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

    • @Cronis
      @Cronis  4 роки тому

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

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

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

    • @Cronis
      @Cronis  4 роки тому +1

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

  • @masterswift9700
    @masterswift9700 5 років тому +1

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

    • @Cronis
      @Cronis  4 роки тому

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

    • @vip51000
      @vip51000 4 роки тому

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

    • @Cronis
      @Cronis  4 роки тому

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

    • @vip51000
      @vip51000 4 роки тому

      @@Cronis спасибо

  • @korsman723
    @korsman723 Рік тому

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

    • @Cronis
      @Cronis  Рік тому

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

  • @ruslanvolovik2745
    @ruslanvolovik2745 4 роки тому

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

    • @Cronis
      @Cronis  4 роки тому

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

    • @ruslanvolovik2745
      @ruslanvolovik2745 4 роки тому

      @@Cronis ок

    • @manOfPlanetEarth
      @manOfPlanetEarth 4 роки тому +1

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

    • @ruslanvolovik2745
      @ruslanvolovik2745 4 роки тому

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

    • @manOfPlanetEarth
      @manOfPlanetEarth 4 роки тому

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

  • @johnwhite9906
    @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
      @Cronis  2 роки тому

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

  • @rodgenk
    @rodgenk 7 років тому

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

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

    Очень круто

  • @6rk5h
    @6rk5h 4 роки тому

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

    • @Cronis
      @Cronis  4 роки тому

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

    • @6rk5h
      @6rk5h 4 роки тому

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

  • @alionabelomenova1075
    @alionabelomenova1075 4 роки тому

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

    • @Cronis
      @Cronis  4 роки тому

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

  • @alex_mech
    @alex_mech Рік тому

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

    • @Cronis
      @Cronis  Рік тому

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

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

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

  • @xfgweb
    @xfgweb 5 років тому

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

    • @Cronis
      @Cronis  5 років тому

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

    • @xfgweb
      @xfgweb 5 років тому

      @@Cronis спасибо.

  • @derzhavin_d
    @derzhavin_d Рік тому

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

    • @Cronis
      @Cronis  Рік тому

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

  • @nikolaysokolov9027
    @nikolaysokolov9027 4 роки тому

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

  • @arslanannaev1292
    @arslanannaev1292 7 років тому +14

    Видео классное, правда не понятна фраза (17:02) "Сколько раз нужно умножить один на два, что бы получить 16?"

    • @Cronis
      @Cronis  7 років тому +2

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

    • @niko-l-
      @niko-l- 6 років тому +24

      Не корректно так говорить, т.к. сколько бы мы раз не умножали 1 на 2 результат всегда будет 2. Правельно вопрос будет звучать так: в какую степень нужно возвести 2, чтобы получить 16

    • @stanislavt5834
      @stanislavt5834 6 років тому +7

      "ПравЕльно будет ..."))))))
      Та, да...

  • @Daoway-f7o
    @Daoway-f7o 2 роки тому

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

    • @Cronis
      @Cronis  2 роки тому +1

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

    • @Daoway-f7o
      @Daoway-f7o 2 роки тому

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

    • @Cronis
      @Cronis  2 роки тому +1

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

  • @awakeupcall5336
    @awakeupcall5336 5 років тому

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

    • @Cronis
      @Cronis  5 років тому

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

  • @zukora
    @zukora 2 роки тому

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

    • @Cronis
      @Cronis  2 роки тому

      Пожалуйста

  • @vladimiradushkevich4178
    @vladimiradushkevich4178 Рік тому

    18:04 > автор не знает математику: "Log N" это и означает что логарифм по основанию 2. 2 - это основание логарифма и в данном примере "является константой которую можно выбросить" это просто не имеет смысла.
    Само основание важно ибо если оно меньше 1 то ф-я убывающая
    в записи bigO опускается 2 но оно всегда подразумевается

    • @Cronis
      @Cronis  Рік тому

      7ое свойство логарифма посмотрите :)

    • @vladimiradushkevich4178
      @vladimiradushkevich4178 Рік тому

      @@Cronis там вывод степени из под логарифма, а не основания (при условии что смотрим в один и тот же источник)

  • @raimbektoleugaziev4845
    @raimbektoleugaziev4845 6 років тому

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

    • @Cronis
      @Cronis  6 років тому +2

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

  • @yakovga
    @yakovga 5 років тому

    Спасибо

  • @СергейЩербак-о3н
    @СергейЩербак-о3н 6 років тому

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

    • @Cronis
      @Cronis  6 років тому +1

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

    • @СергейЩербак-о3н
      @СергейЩербак-о3н 6 років тому +1

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