0: Хорошо. Продолжаем, как нам искать оценку сложности алгоритмов. На самом деле, в самом общем случае, когда у вас огромное количество строчек кода, когда у вас сложный проект, в котором взаимодействуют различные отдельные модули, в разных потоках происходит

1: Какая-то там какое-то взаимодействие клиента с сервером и вот это все проанализировать конечно сложно, но вполне себе возможно для отдельных частей. В общем случае вам необходимо найти

2: Ту самую зависимость количества операций, элементарных операций, подчёркиваю, от размера входящих данных н.

3: Соответственно, вам надо найти функцию, которая описывает эту зависимость. И в этом, конечно, вам может помочь математика и различные инструменты оттуда, но как нам это делать в прикладном варианте, так хотя бы более менее в простых случаях в целом.

4: Есть алгоритм, состоящий из 3 Шагов. Нам необходимо дать оценку каждой отдельной операции. Обратите внимание, не вызову метода, не строчки, а отдельно элементарные опера, вообще отдельные операции. Не обязательно элементарно.

5: Операции, а потому что в данной строчке, например, у нас сложение, да, отдельная операция, присваивание, отдельная операция. Более того, мы понимаем, что под капотом там у нас, поскольку плюсы, да, это сложение, это будет вызов какого-то метода, выделится место на стеке, мы

6: Скопируем туда значение икс игрек, а икс игрек это адреса каких-то объектов в памяти, да, мы их скопируем то есть скопируем какое-то количество Ноликов, единичек. Это как раз-таки какая то отдельная элементарная операция и так далее и тому подобное. Очень

7: Много вещей, но мы посмотрим, насколько глубоко надо погружаться. Ну то есть дать оценку каждой операции. 2, проанализировать, как часто каждая операция повторяется. То есть, есть ли какая-то зависимость, например, какая-то операция повторяется там 1 раз только, или она

8: Она повторяется только 5 раз, то есть константное количество раз, да? Или же её количество, сколько раз она будет выполнена тоже каким-то образом зависит от, н, да, от размера входящих данных, например, если у нас

9: Лист 1, 2, 3, то, понятное дело, при сортировке мы будем выполнять больше действий непосредственно по сортировке, да, то есть, чем больше элементов, тем больше каких-то внутренних действий, которые мы со временем узнаем, будет

10: Выполнено да, элементы будут переставляться местами банально, но при этом вызов метода sort, он будет выполнен 1 раз. То есть как бы какой бы там массив не был бы ну 1 раз вызвали и все. Вот соответственно анализируем сколько раз

11: Выполняется эта операция. 3 пункт. Нам надо выбрать максимум из 2 пункта, то есть выбрать самую тяжёлую, самую часто повторяющуюся операцию. И это и будет ваша оценка. То есть, по сути это будет

12: Такой самый быстрорастущий член вашей функции, получившейся. Вот ну давайте посмотрим на каких-то примерах, как же это все делается. Напоминаю в качестве элементарных операций.

13: Которые имеют константную оценку, то есть они выполняются за константное время, как бы условно выделенный какой-то одинаковый промежуток. Мы берём элементарные операции, то есть присваивание, сложение, вычитание, умножение какое-то

14: Равнение, да, какие-то логические операции and или, ну, ор, соответственно, n.

15: И, в принципе, все, да, ну, такие базовые вещи, вызов метода тоже, можно сказать, это элементарная операция, но вызов метода, он же приводит к выполнению какого-то набора действий. И зачастую мы не знаем, какого именно поэтому вызов метода, по сути, имеет какую

16: Какую-то другую сложность, не от единицы. Выполнение метода. Хорошо, давайте смотреть каждой операции. Ну, мы здесь видим это, по сути, просто присваивание, элементарная операция, её сложность.

17: Единицы. Тет от единицы. Здесь тоже тета от единицы. Присваивание, здесь сложение о, от единицы тет от единицы. Да, небольшая небольшая заметочка. Мы, в принципе, зачастую.

18: Говорим о там, о Тен квадрат. То есть вы, как правило, в повседневном как бы, общении говорите о Тен квадрат, то есть вы даёте ограничение сверху, потому что его проще получить, чем оценку более конкретную тета и

19: Как бы на глазок это ещё хоть как-то можно сделать. Вот, ну и плюс с клавиатуры банально неудобно вводить тета, поэтому зачастую, говоря об о большим, об большом подразумевает либо оценку сверху, либо тета, как бы это

20: Не сильно, принципиально. Просто особенности выражений. Окей, тета от единицы. Здесь присваивание тета от единицы. Все, да, как бы базовые операции мы взяли вот такой вот наборчик за базовые операции, может быть, ещё дополнительно узнаем по

21: Позже какие-то ещё. Ну ладно далее 1 пункт у нас выполнен алгоритм. 2 пункт. Сколько раз повторяется эта операция. Ну понятное дело, 1 раз, 1 раз, 1 раз, 1 раз и далее, по сути вот что это означает.

22: Да что нам с этим дальше делать? Мы можем перемножить значение слева от нашего тета и внутри скобки, то есть, по сути, смысл какой, представьте себе, мы повторяем n раз какую-то 1 операцию.

23: Со сложностью тета от единицы да, r n стремится к бесконечности это размер входящих данных, то есть, грубо говоря, чем больше n, тем больше элементарных операций мы повторим, то есть тем больше работы будет совершенно, и по сути мы здесь.

24: Можем вот так вот сделать, занести н. В внутрь скобки, н. Умножить на 1, да, и поскольку мы помним, что нам не принципиально константы, мы откидываем константу, ну или умножаем просто n на единицу и получаем оценку тета от н.

25: То есть, действительно, если у нас какая-то операция повторяется, н, раз, ну, её общая сложность в контексте нашего алгоритма тет н вот, поэтому здесь мы единичку вносим внутрь, скобок перемножаем, так, блокировать.

26: И получаем вот эти вот оценки среди всех этих оценок. То есть можно сказать, что наш алгоритм имеет вот какую-то такую вот оценку, тета от единицы, плюс тета от единицы, плюс тета.

27: От единицы, да, в целом это можно вот так вот объединить. Это 1 + 1, + 1, + 1, + 1. Помним, что нас интересует в нашей получившейся функции самый быстрорастущий член и нам не важны

28: Константы. Ну, в данном случае мы как бы можем, конечно, сложить, да, 4 единички, получить 4, это 4, но это не имеет смысл, да, это просто какая-то константа, от которой мы избавляемся и указываем просто единицу.

29: То есть вот как-то так в самом простом варианте можно проанализировать оценку сложности алгоритмов. Напоминаю, алгоритм это последовательность каких-то действий, не углубляясь сильно в математику, это последовательность действий, да, она конечная, причём

30: Что очень важно для алгоритма. Ну что здесь в качестве как бы, размера входящих данных можно взять, да, ничего, да, то есть в целом нет такого, что мы

31: Имеем какие-то входящие данные для данного алгоритма.

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

33: Могут быть большими да, огромными и на самом деле вы должны понимать что чем больше значение там, тем больше в нём банально ячеек памяти как бы занято тем больше Ноликов и единичек, то есть на самом деле, чем больше int, тем менее

34: Производительно сложение вот здесь вот в особенности, да, и банально большие числа, там, 10, не знаю, в 20 у вас не влезут в процессор, да, не влезут в регистры процессора в кэш процесс.

35: И поэтому даже на таком простом примере с большими икс и игреками сложность сложения будет большой, потому что у вас включится в игру так называемая длинная арифметика.

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

37: И, естественно, это не очень производительно. Вот, но это так немножко забегание вперёд. Просто имейте ввиду, что даже по, в таком примере не все так однозначно. Это как раз-таки ещё 1 нюанс, ещё 1 доказательство того, что наша оценка, она именно пред

38: Назначено, что не для точного оценивания количества операций, а для примерного, но с использованием каких-то строгих утверждений, строгих правил. Хорошо.

39: Далее тут же ещё можно другой нюанс отметить смотрите, можно было, конечно, ставить такую вот оценку, но от того, что вы сделаете оценку, например, н квадрат + 2 или тета от n 2 n + 55 и 5.

40: Вы не получите более точную оценку, да, из того, что я перед этим в нескольких видео говорил, можно сделать такой, собственно, вывод. То есть вы, конечно, скажете, ну это же более конкретная функция. Типа, да, это не

41: Просто какой-то н квадрат, да, это более приближённая к реальности типа оценка, но на самом деле это не влияет на ни на что. Да, мы все равно не знаем точную функцию, мы все равно не знаем, как именно она

42: Себя ведёт на малых значениях n. И мы все равно рассматриваем эту оценку при n. Стремящемся к бесконечности, а когда н. Стремится к бесконечности, вам в принципе пофигу тут н квадрат + 2 или 2 n + 55 и 5 у вас.

43: Стремится к бесконечности. Все остальное не имеет никакого значения. И тоже самое здесь и 4, и 1. Это константа. Поэтому мы не указываем точные константы. Мы в случае таком, да, когда константа в оценке, указываем просто единицу, показывая, что это константа, а не переменная, и все.

44: Теперь давайте перейдём к более сложным примерам. Да, в правом верхнем углу у меня как раз-таки алгоритм, то есть найти, дать оценку каждой операции, понять, как часто повторяется каждая эта операция, получить оценки промежуточные Ида.

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

46: Здесь сложение от единицы, здесь присваивание от единицы. Здесь print. Мы не можем сказать, что print это от единицы. Это же вызов метода. Понимаете? Вызов метода, что такое метод это список каких-то действий.

47: Вот, соответственно, метод может на самом деле иметь вот этот весь метод, оценку от н. Н. Квадрат n в Кубе н. Факториал и так далее. Он просто может повиснуть при выполнении внутри вашей программы. Что поделать.

48: Поэтому мы не можем дать просто рандомную какую-то оценку. Метод это алгоритм. И у алгоритма должна быть оценка какая-то, если мы её не знаем, нам надо её узнать. Ну все легко и просто, понимаете.

49: Я бы с радостью вам дал какой-то Лёгкий путь, но, к сожалению, его нет, да, тут шорткат особо не предусмотрен, поэтому что мы делаем в такой ситуации, мы не знаем оценку, мы не можем её понять просто так. Тогда у нас есть несколько вариантов google.

50: Google, мы ищем информацию или какой-то уже имеющийся анализ о том, какая сложность имеется у функции print. Да, не всегда это возможно. То есть не всегда вы можете найти эту информацию для

51: Более, когда используются какие-то сторонние библиотеки. Ну мало ли, никто не задавался этим вопросом. Или библиотека старая, или она устаревшая, какая-то богуча Логовая, или, может быть она вообще никому не нужна, или, может быть, вы сами разрабатываете эту библиотеку? То есть вы не можете загуглить, да?

52: Ну искусственный интеллект, я тут даже не говорю. Искусственный интеллект с научными какими-то выкладками, с математическими выкладками вообще в печали находится до сих пор, да, поэтому не упоминаем потом

53: 2 вариант это документация понятное дело, что в реальности вы, скорее всего, все-таки пойдёте сначала в google, но давайте мы хотя бы

54: Примерно, скажем, вот так вот все-таки сначала, наверное, в документацию, но реальность такова, что не факт, но ладно, вот соответственно, документация в документации вполне себе возможно найти оценки для тех или иных методов, особенно для

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

56: Часто сортировать вот с такими оценками вообще не надо. Может быть даже вы не сможете даже 1 раз отсортировать, особенно если попытаетесь отсортировать какие-то там большое какое-то количество элементов. Вот. Поэтому там важно, конечно, понимать, как влияет.

57: Чужой код или просто метод сортировки на вашу сложность алгоритма? Ну что поделать? Да, смотрим, соответственно, в документацию далее. Но если вообще нигде ничего нет.

58: Исходники исходники, в данном случае python это web python, да, самая стандартная реализация, самая широко распространённая, понятное дело, если что, в какую-то другую надо будет лезть, но да, исходники не на.

59: Пайтона не все на пайтоне, по большей части они на си написаны, да что поделать от того, что вы изучаете конкретный язык. Ну, вам резко другие языки программирования не блокируются. Да нет такого, что вот вы изучили.

60: 1 высокоуровневый язык. И теперь дальше заново надо будет изучать там, не знаю, какой-нибудь си плюс, плюс потом изучили пайтон си плюс плюс, ну вы же ничего не знаете про сишарп надо заново изучать. То есть, ну на самом деле большинство Языков программирования, они очень сильно друг на друга похожи, поэтому даже

61: Со знаниями пайтона, пусть он как бы очень многое скрывает в си коде вы вполне можете разобраться. Тем более вот сейчас поиграюсь, углубившись в особенности пайтона его работы, работы с памятью работы опять

62: Особенности работы компьютера, алгоритмов и так далее. Вот в исходниках вы, соответственно, понятное дело, не факт, что найдёте точную оценку, ну и ладно, вы получите код, то есть вы получите какую-то последовательность действий, и вы также может

63: Можете её отдельно проанализировать и дать ей какую-то оценку, ну хотя бы, например, оценку сверху. То есть, чтобы понять, ну насколько вообще все печально, как бы.

64: Как-нибудь ограничили сверху, может быть как-то ограничили снизу, да, поняли, что, например, ограничение сверху у нас оно выглядит как-то там, ну как, например, как, н, в квадрате ограничение снизу выглядит, ну, как-то типа

65: То есть наша тета находится где-то в этом промежутке, она может быть равняться. Тета атен квадрат, тета атен, да, тетта н лог. Но в целом даже хотя бы такой анализ уже даёт вам.

66: Вы нигде не накосячили? Даёт какую-то возможность маневрирования? Да, хорошо. С таким, с такими оценками нам вполне можно использовать в нашем коде данный этот

67: Как его?

68: Данный метод, да, или данную библиотеку. Окей. Но что, если исходников нет, не все открыто, да, а библиотеки бывают вполне себе закрытыми, но их использовать приходится. Что ж, тогда, в принципе, остаётся, наверное,

69: Последний вариант это собрать статистику, к сожалению, собрать статистику это очень сложно.

70: Даже примерную, понимаете? То есть не просто так существует выражение, да, что существует 3 вида лжи ложь, наглая ложь и статистика. Нельзя

71: Просто взять, поставить секундомер здесь таймер, поставить здесь таймер и все. Вот функция выполняется за 5 миллисекунд ей классно используем. Да, как раз-таки зачем?

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

73: Z равное 5 а что если z будет равняться 5 в 10, вы уверены, что ваш принт Инта займёт столько же там 5 миллисекунд или вдруг из за того, что он коряво реализован на 5 в 10 или 5 100 у вас print займёт?

74: 5 секунд. Ну че то 5 миллисекунд 5 секунд это как-то немножечко так, не очень хорошо звучит, да, вот. Поэтому да, и в конце Концов не просто так у нас есть какие-то

75: Отдельные области науки, да, типа масс статистики, которая говорит о том, как именно с данными работать. Поэтому статистика, к сожалению, ну это прям отдельная проблема, и по хорошему привлекать надо отдельных специалистов, да, но

76: Хотя бы в общих чертах вы можете попробовать, да, что сделать. Вы можете попробовать выполнить ваш метод при различных входящих данных, то есть при равняет равном нулю единице.

77: Тройки, четвёрки, да, каких-то малых n, при каких-то средних, н, там 100, 200, там, 250, 1000 10000, 3 и так далее, при каких-то огромных, н, там, 10, 5.

78: 5, 3, 10, 10, 10, 20 и так далее. При каких-то нечётных. Н, то есть 2 четы, в смысле, 1, 3, 5, 7, при каких-то чётных, н, 2 и так далее. Может быть.

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

80: Хаотично производительность может упасть. И это тоже как раз-таки к разговору, да, проблематичности сбора статистики по эффективности ваших методов и программ, но хотя бы вот так вот всевозможные варианты перебрав и собрав статистику

81: Получив какое-то среднее время выполнения какую-то, может быть функцию, ну вы уже можете сделать вывод о эффективности или неэффективности вашего метода метода библиотеки, в принципе вариант

82: 5 есть порассуждать.

83: Но, как бы во время рассуждений вам надо будет к чему-то из этого обращаться, да, просто так порассуждать. Типа, ну вот, а вот, да, принт, не должен быть. Ну, типа, че, дураки, что ли, писали? Нет, ну, значит, эффективно.

84: Да, это вот у меня какие-то такие ассоциации с пунктом порассуждать. Поэтому вот 4 основных варианта того, как можно узнать оценку для сложной операции, для комплексной, для составной операции, для элементарных. Это все просто они выполняют

85: Выполняется в целом за константное время. Окей, ну, собственно с принтом, что с принтом в контексте н зет, да, где у нас z это интовские значение, если мы говорим о

86: Малых. Н, да, то есть те, которые, например, условно говоря, до, там, знаете, 2 в 8 какой-нибудь степени, то можно сказать, что принт имеет оценку сложности от единицы. Но вообще, да, это на самом деле,

87: Отдельную можно задачку дать на door ball, например?

88: Какая у него сложность. То есть это можно проанализировать с помощью опять-таки, вот этих 4 пунктов, да, и получить, например, такую оценку, что логарифм, н, где print от н и н, это какое-то значение

89: Наше собственно интеджер, то есть integer, это же какое-то целочисленное значение в десятичной системе исчисления, оно представлено как-то в виде Ноликов и единичек, и чем больше число, тем больше Ноликов, единичек, чем больше Ноликов единичек.

90: Тем больше нам надо выполнять действий по превращению их в строку, например, 5, там, 1, 2, 3 и так далее. Соответственно, чем больше число, тем больше работы будет произведено, да, как именно, мы не знаем, но это можно опять

91: Я уже сказал получить, например, из исходников. Вот ещё 1, кстати, нюанс. Смотрите, если какая-то зависимость есть, это не означает, что зависимость линейная, не попадайтесь в такую ловушку. Да, слова есть зависимость, говорят только

92: Том, что есть зависимость, а варианты зависимости я вам до этого показывал, там n factorial может быть н лог н и абсолютно другая функция какая бы то ни было возможная в мире не обязательно те которые на картинке это просто

93: Часто встречающиеся. Вот, поэтому мы получаем здесь print. Соответственно, логарифм зет. Ну, в данном случае мы не, н, какую-то мифическую, здесь у нас z это размер, собственно, зет и все.

94: Логарифм зет по основанию 2, но основание мы откидываем по правилам логарифмов.

95: Ну, мы можем логарифм перевести из 1 основания в другое, вынеся константу, вспомните эти правила, поэтому мы не сильно обращаем внимание на основание алгоритма логарифма. В смысле, в оценке сложности алгоритмов. Вот. Ну что ж.

96: И вот мы получили, да, сколько раз выполнится этот принт 1 раз, да? Ну, мы, соответственно, получаем здесь тета от логарифма, н, 1 раз выполняется. Единичку, мы заносим в скобки. И конечная оценка, у нас конечные оценки выглядят вот так, да, это, по сути, все склады.

97: Друг с другом выбираем самый быстрорастущий член по нашему алгоритму. Это логарифм зет. То есть вот такой простой элементарный набор действий уже имеет оценку логарифм зет тета от логарифм.

98: Можно для общего случая написать логарифм. Н да, но это не принципиально. То есть вы должны понимать, что когда я говорю про, and это размер входящих данных, переменная может быть любой, вообще любой, ну, как бы that в данном случае

99: Потому что мы понимаем, чем больше z в данном случае наша переменная, тем больше операций будет, поэтому как бы логарифмическая зависимость от нашего числа z. Да, у вас на самом деле могут быть оценки какие-нибудь тет от x. Да, где x это?

100: Не знаю, количество чётных чисел в строке. У вас может быть оценка? Тета от игрек? Где игрек это?

101: Количество, не знаю, количество воскресений в 5 месяце каждого года, за последние, там, 10 лет. Ну, можно придумать такой алгоритм, который, в принципе, будет зависеть от подобных вещей.

102: Без проблем, что поделать. Да, это те данные, которые поступают на вход алгоритму. И чем они больше, соответственно, тем больше действий мы выполним. Все логично. Единственное, наверное, здесь можно сказать,

103: Давайте ещё следующую вещь. Смотрите, когда у нас имеется несколько вещей типа n плюс игрек. Ой, давайте более конкретный вариант. Это от

104: Давайте возьмём в и е умножить и так далее. Это нельзя сократить. То есть нельзя сказать, что это будет равняться там тета от в квадрат или е квадрат.

105: Или как-то там просто в или ещё что-то. То есть это 2 разные переменные и если они непонятно как зависят друг от друга, то мы не можем их сократить. Это как бы все хорошо да окей. У нас функция, которая зависит от

106: 2 аргументов в её в данном случае так получилось без проблем. И как, когда такое возможно на самом деле, что здесь за в мы с вами во 2 семестре будем рассматривать графы в очень

107: Структуры данных, которые как раз, как я говорил, 1 из вариантов представления в памяти, да, это линкит листы. Так вот, и используются там в различных базах данных или каких-то

108: Подобных эффективных структурах данных. Так вот, что у нас в графе есть, да, не сильно пока, углубляясь туда, у нас есть вершины и связи между ними, то есть ребра. Так вот, в это вертекс

109: Что такое-то есть вершина е это edge.

110: Age ребро, соответственно, вот вам вершины, вот вам ребра, и у нас есть алгоритмы, которые имеют подобные оценки, что здесь за модуль, это количество элементов, то есть количество вершин, количество

111: Рёбер. И получается так, что наш алгоритм, да, количество операций в нашем алгоритме, зависимость количества элементарных операций от размера входящих данных. Так вот, этот размер входящих данных определяется количеством вершин. Умно.

112: На количество рёбер. И вот в таком варианте у нас рёбер побольше, чем вершин, да, ещё можно докинуть парочку. С другой стороны, я могу нарисовать вот такой вот граф. И это граф просто несвязный. Мы со временем зна,

113: Что это такое? И окей, рёбер мало. Обрати внимание. Да, тут вообще 1 ребро. Ну ладно, получается так, что количество рёбер будет не так сильно влиять на результат, но, тем не менее, наш алгоритм до

114: Нужно учитывать и то, и то поэтому если в оценке сложности у вас встречаются разные какие-то переменные, да, которые никоим образом не зависят друг от друга, тогда, к сожалению, вы не можете от них избавиться, но

115: Мы с вами будем смотреть дальше у нас может быть такая ситуация, когда 1 переменная зависит от другой и зависит от, например, размера входящих данных в таком случае x зависит от н и зависит от x y.

116: И также зависит по сути, от н, как-то косвенно. И мы, по идее, можем вот эту зависимость выразить. То есть, если у нас есть связь между переменными, то в идеале нам надо все выражать через н, да, это на будущее. Запомните, но если они независимы,

117: Мы, ну.