0: Идём далее. И теперь такой более сложный примерчик. Причём этот пример, он на самом деле показывает частую ошибку, которую могут совершить при оценке сложности алгоритмов. То есть в различных источниках мы, конечно,
1: Понятное дело, может быть что-то дополнительно читаете это отлично. Дополнительно разбираетесь альтернативные какие-то мнения, да, может быть где-то я ошибся, где-то, что-то неправильно сказал, там оговорился, опечатался и так далее. Всякое возможно. Вот. Но опять-таки в дополнительных 100
2: Тоже бывает, конечно, некорректная информация. Вот. И во многих источниках, особенно таких прикладных, вам говорят, цикл в цикле это н. Квадрат.
3: К сожалению, нет. В общем случае у вас нет каких-то правил, которые говорят о том, что та или иная синтаксическая структура, конструкция, то есть for while какие-то там и прочие вещи, они выполняются за какое-то конкретное
4: Время на самом деле цикл фор, как мы показали, он может иметь сложность. Тета от единицы, да, а он может иметь сложность. Тета от en. Мы получали там тета от and логен или что-то в этом дух.
5: Или там логарифм, н в квадрате. Ну, в общем, какие-то были варианты у нас правильно. То есть на самом деле не все так очевидно. И единственный вариант получить оценку для вот цикла в цикле адекватную оценку, это использовать, в общем то, тот же самый алгоритм.
6: То есть проанализировать все операции. Я понимаю соблазн большой цикл в цикле н. Квадрат, но нет такого правила. И мы с вами разберём. У вас там в домашках будут задачки, где н квадрат не будет приводить к
7: В смысле, вложенный цикл не будет приводить к н квадрат, он, может быть, к более худшим оценкам будет приводить или к более лучшим. Это уж со временем узнаем, да, но, увы, ну, собственно, выполняем наш
8: Алгоритм сначала только заблокировать надо. Смотрим. Так, давайте это я побольше на самом деле сделаю. Так. Вот тут точно видно было и мы пытаемся теперь это проанализировать. Так.
9: Input у нас имеет тета от длины инпута. Давайте я помечу отдельно как-то там, допустим, н равняется длина инпут, то есть то, что введёт пользователь, тета от н.
10: Здесь от единицы здесь перевод б в int у нас имеет сам по себе да тета от н квадрат здесь у нас тета от единицы здесь у нас range взятие 1.
11: Элемента от единицы. Взять 1 элемента от единицы в смысле генерация элемента здесь взятие элемента из ренджа здесь int b. Сама по себе эта отдельная операция имеет сложность как мы уже знаем, тетот н квадрат то есть да, где н это
12: Мер нашего нашей строки, которая входит в качестве аргумента в нашу функцию int рейндж тета от единицы изолированно друг от друга здесь тоже тета от единицы, здесь только давайте не e r g. Все так.
13: Вот так вот сделаем джей принт б. Да, опять-таки принт б б. Это у нас строка, поэтому здесь в целом тета от длины б.
14: Ну, можно сразу сказать, это длина нашего импута, то есть те таатта. Окей.
15: Здесь у нас н квадрат, действительно, б, это, собственно, длина нашего импута. Мы взяли н равное длину импута, поэтому здесь, н, квадрат, здесь у нас тоже тет от н квадрат, здесь у нас тет от н сколько раз.
16: Повторяется тайная операция. 1 раз, 1 раз здесь 1 раз, 1 раз здесь сколько раз икс икс это у нас, ну, какое-то значение, да, которое мы не знаем однако мы не
17: Конечно x. Да, это какое-то значение, которое, по сути, получается из строки, которая введена пользователем, но, по идее, можно предположить, что чем больше строка, а мы же говорим об интах, поэтому чем больше строка, которую пользователь ввёл, тем большее значение.
18: X. Соответственно x зависит от б. Ну и b это наша строка и зависит от размера этой строки чем больше размер строки, тем больше естественно у нас будет.
19: Циферок в числе тем больше элементов сгенерирует наш рейндж, тем больше итераций цикла будет произведено. Единственное, я сейчас что-то осознал. Вероятно, перед этим я говорил, что типа, н, равняется там input, то есть, понятное дело, там
20: Подразумевалось не н точнее, да, там было, что в духе б равняется инпут. Ну, подразумевалось, что указана была длинна. То есть, потому что как бы, зависит от строки просто так, непонятно что, а вот от количества элементов
21: Строке уже действительно можно или там от размера строки, от объёма строки, от объёма памяти, который занимает объект и тд. И тп. Ну возвращаемся к нашему этому примеру да, 1 раз 1 раз, 1 раз тут соответственно, раз у нас x пропорционален б.
22: Причём у нас линейная зависимость x y длины б. Мы поэтому 1 раз это по сути повторим это тоже n ras. Далее сколько раз я повторю вот это вот все.
23: По идее, вот эту вот операцию, да, я этот цикл сам по себе буду повторять на каждой итерации цикла внешнего. Правильно? Всего у меня итерации внешнего цикла будет, н, то есть
24: Yeah, н раз повторю вот этот цикл. А в этом цикле я буду выполнять, что я буду выполнять каждый раз приведение б к Инту, а эта операция имеет н квадрат соответственно.
25: Range я буду выполнять тоже какое-то количество раз да какое количество раз это я буду выполнять это я буду выполнять и это я буду извиняюсь вот это вот да, выполнять на каждой итерации цикла генера
26: Нового элемента, взятие нового элемента. И более того, каждый цикл буду повторять 1 раз. То есть вот эту штуку я повторю, внутри нашего цикла получается сколько раз поряд
27: Н раз тоже, да, вот эту штуку я повторю сколько раз, н, 1 раз именно внутри нашего внутреннего цикла мы независимо от всего предыдущего кода. Сейчас давайте рассмотрим внутренний цикл, потому что
28: Действительно не зависит. Далее вот это я повторю н раз и это я повторю тоже по идее n ras. Правильно, но поскольку этот цикл вложен и выполняется каждый раз на каждой итерации внешнего цикла, то все эти действия я
29: Повторю дополнительно n. Раз. То есть вот это я повторю н раз ещё это я повторю н. Раз это я повторю не 1 раз. R n. Раз. Да ну, потому что значение посчитается для ренджа 1 раз, только когда у нас будет запу.
30: Цикл, цикл будет запущен. Н раз. Поэтому н раз я вот эту операцию за н квадрат буду выполнять. И. Б. Мы тоже выполним, получается, н раз.
31: Уф, что-то страшное получается здесь, да, мы здесь 1, 1 убираем, в принципе, н, уходит под скобочку отн здесь у нас тоже отн уходит под скобочку, да.
32: Так, от н да, правильно. Здесь у нас н на н н квадрат умножаем от единицы на н квадрат сюда уходит н квадрат, н квадрат умножаем, на н получаем, соответственно, н в Кубе, здесь, н на н в квадрате, н в квадрате умножаем на наше н.
33: Получаем н. В Кубе. Здесь мы умножаем на н. В квадрате и умножаем на единицу. Получаем оценку финальную н. В квадрате. Все. То есть мы выполнили 2 пункта из нашего алгоритма. И на это ушло довольно много времени, да, потому что, как бы та
34: Пересечения различные были и так далее, но что поделать.
35: И теперь выбираем максимум. Ну максимум у нас здесь это, это от н, в Кубе.
36: Вот как-то так. То есть вложенный цикл, казалось бы, но даёт нам н. В Кубе итераций. А все почему? Потому что отдельные операции внутри циклов, они не выполняются за константное время. Поэтому у нас
37: Накладываются некоторые сложности друг на друга. И получается довольно-таки грустная оценка для такого алгоритма. Вот тут очень важный нюанс прямо-таки. То есть если вы вдруг запутались в том, как у вас циклы
38: Выполняется цикл в цикле, например, да, здесь вы не понимаете, а почему у нас инд б выполнится, как я сказал, н раз, да, почему вот здесь вот n квадрат раз выполнится взятие 1 элемента. Ну, тогда получается, что
39: У вас не наработался такой механический навык программирования, когда вы чётко представляете, что делает for, да, как и сколько раз выполнится тело цикла for да, что будет, если
40: Цикл в цикл вложить. И это, к сожалению, никакая нейронка, никакие курсы вам не дадут, никакие лекции, никакие видео, никакие книги не дадут. Это банальная вещь, которую я сказал вам на 1 паре. Программирование.
41: Ну, даже, наверное, программирование не то, что банальная вещь, да, но практика. Давайте назовём так непосредственно самостоятельное написание кода, разработка алгоритмов, реализация алгоритмов.
42: Потому что без этого и оценку сложности будет крайне проблематично анализировать и понимать структуру данных и реализу.