Итак, продолжим. Мы хотим научиться как-то более менее строго заранее понимать, что один алгоритм эффективнее чем другой. На примере lower bound и find if можем искать одно и то же число с помощью lower bound и с помощью find if указывая эту функцию. Как можно было заранее понять, что find if медленнее? Мы конечно уже обсуждали что find if просто по сути дела цикл for и идет сначала диапазона, пока не найдет нужный элемент, a lower bound выполняет бинарный поиск. Более того, мы даже обсуждали, что этот самый бинарный поиск работает за логарифмическое время, то есть он делает порядка логарифма операций от вот этого размера диапазона. Давайте обозначим размер диапазона за N, тогда можно сказать что lower bound работает за логарифм N и он а find if в худшем случае работает за N. Заметьте, в худшем случае, если то число, которое мы ищем, окажется в конце, или даже в середине, будет сделано порядка N операций, но если же это число, которое мы ищем, окажется в самом начале, тогда конечно find if будет работать быстро, но мы говорим о худшем случае. Это важно. Итак, логарифм N и N, понятно, что N больше чем логарифм N, особенно когда N велико. Давайте во-первых договоримся, что основание логарифма будем считать двоичным, хотя это и неважно, это во-первых, а во-вторых, конечно мы очень грубо сейчас оцениваем количество операций, которое будет сделано в lower bound и find if. Конечно, в lower bound происходит на каждом шаге не одна операция на каждом из логарифма шагов, а может быть несколько. Сравнение, присваивание, что то еще. Давайте считать, что константа нам не важна, то есть если например, у нас в реальности там 8 логарифм N и девять N операций, это не важно, потому что когда N велико, все равно N будет больше, чем логарифм N, какая бы константа там ни было, в частности поэтому мы можем не писать основание логарифм, потому что, как вы наверное знаете, логарифм, взятый по одному основанию отличается от логарифма взятого по другому основанию только лишь константным. Неважно, давайте считать, что логарифм двоичный. Итак, мы ввели обозначение N и с помощью этого обозначения можем выражать сколько примерно операций делается в алгоритме, который нам интересен. Это мы обсудили простые алгоритмы, lower bound и find if, с которыми все в общем то понятно, а у нас более сложная программа, в которой есть, например, цикл. Давайте мы в цикле пройдем по некоторому контейнеру number to find и для каждого элемент этого контейнера вызовем lower bound. Поищем это число в другом контейнере и затем выполнить какую-то простую операцию, например, х умножить на 2. Сколько операций будет производиться в такой программе, сколько этот код будет работать. Во-первых, у нас есть внешний цикл for, который делает понятно сколько итераций, столько итераций, каков размер контейнера numbers to find'. А дальше, в каждой из этих итераций сколько мы делаем операций, мы запускаем lower bound, который работает логарифм от размера контейнера V, и потом еще одна операция тратится на умножения х на 2. Итого получаем такое выражение для грубого количества операций, number_to_find.size, это сколько итерации у нас в внешнем цикле for, умножить на сложность одной итерации. Сложность одной итерации, это логарифм от V size плюс один. Один это та самая мелькая операция, х умножить на два, в принципе уже понятно, что это плюс один никак особо на эту сложность не влияет. Итак, чтобы оценить сложность одной программы, по сути нам нужна простая математика: сложение и умножение, причём ещё раз обращаю внимание, мы всё это оцениваем для худшего случая, понятно что в реальности, когда вы пишете [inaudible] какую-то программу, которая поступает на вход какие-то данные от пользователей просто данные из какой-то базы данных, вы не можете контролировать эти данные вы не можете полагаться на то, что они будут хорошими, так и в наших тестах, в наших задачах. Если вы отправляете нам на проверку какую-то программу, уж будьте готовы к тому, чтобы придумать такие входные данные, на которых ваша программа будет работать долго, поэтому вот здесь надо быть пессимистами и оценивать производительность для худшего случая. Однако надо понимать, что бывают случаи, на которых ваша оценка по сравнению lower bound и find if например, будет не верна. Давайте вернемся к нашему примеру с этим сравнением. И будем искать не какое-то число и середины, мы искали число 7 миллионов, конечно до него find if шел долго, а давайте поищем, например, число один, которое буквально в начале стоит, и давайте запустим сравнение lower bound и find if, которые ищут число один. Итак, и то и другое работает мгновенно. Давайте, чтобы их различить, мы сделаем не десять поисков, а, скажем, миллион и посмотрим, что эффективнее. Какой из алгоритмов эффективнее найдет число, которое находится в начале массива, [inaudible] отсортированного массива. Итак, find if оказался эффективнее в этот раз, find if нашел нужное число уже на второй итерации. А lower bound всё также сходил с обидарным поиском, он смотрел на диапазон целиком, потом на первую половину, на первую четверть, и так далее, и так далее, всё равно сделал логарифм [inaudible] операции, в то время, как find if сделал по сути, ну условно всего две операции. Итак, это случай, в котором find if стал лучше, но, мы будем говорить о худшем случае. Итак, Давайте обсудим сложность тех алгоритмов, которые мы уже проходили в предыдущих курсах. Какой вообще бывают сложности, бывает сложность один или константная сложность, когда вы сделали какие-то операции, сложность которых не зависит от размера входных данных, например, сделали какую-то арифметическую операцию - умножили х на 2 или обратились к какому-то элементу вектора. Эти операции выполняются быстро, буквально несколько операций и говоря, что сложность таких операций константное или единица. Бывают операции, сложность которых зависит от размера входных данных логарифмически. Например, lower bound, будучи вызванным правильно, ан не от сета, например, от отсортированного вектора или поиск во множестве или в словаре. Эти операции логарифмические, они имеют логарифмическую сложность, то есть эта сложность равна, с точностью до константы, логарифму размера контейнер, а в котором мы ищем. Какой еще бывает сложность. Сложность бывает линейной, например, у find if, и сколько он сделает операций в худшем случае, ну порядка размера контейнера, то есть N, столько же примерно операций сделает мин элемент или вообще произвольное цикл for у которого итерации небольшие. Если вы пишете цикл for по контейнеру размера N и у вас каждая итерация константа, имеет константную сложность, тогда этот цикл for будет иметь линейную сложность. Часто говорят, что просто такие алгоритмы линейные. Какой еще бывает сложность? конечно, бывают разные комбинации из N логарифма или вообще любых других функций, например логарифм от логарифма, если у вас какой-то сложно интересный алгоритм или алгоритм в квадрате умножить на N или что то еще, но есть стандартный алгоритм, сложность которого знать нужно в любом случае, это алгоритм sort. Когда вы сортируете какие-то простые объекты с простым оператором сравнения, например, числа, такой алгоритм будет работать N умножить на алгоритм N. Сложность NlogN, сложность стандартного алгоритма sort. Итак, бывает сложность константное, логарифмическое, линейное, NlogN ну и на самом деле разные комбинации всех этих величин. Когда вы хотите узнать сложность от алгоритма, например, ищите в интернете, вы увидите либо конкретное слово, константное, линейное, логарифмическое, или запись чуть более формальную, а именно О большое от логарифма N, например, что формально это означает, О большое от логарифма N, это означает, что алгоритм работает не больше, чем логарифм N с точностью до константы, ну или, например, вот на слайде пример, от NlogN, это означает, что алгоритм работает не больше чем NlogN с точностью до константы. Причем здесь есть небольшой подвох, О большое означает оценку сверху и в принципе она может не достигаться вообще никогда, т.е. когда вы читаете, что алгоритм работает О большой от NlogN, может оказаться так, что он работает за константное время, просто вам дали не точную оценку сверху, просто будьте к этому готовы. Хорошо. Вот мы поговорили о том, какие сложности имеют изученные нами алгоритмы, но как же, встретив неизвестный вам стандартный алгоритм, узнать сложность его работы? Тут два варианта. Либо вы понимаете как он работает на самом деле и по сути понимаете какая будет его сложность, например, lower bound работает с помощью бинарного поиска, бинарный поиск работает логарифм, поэтому lower bound тоже будет работать за логарифмом, быстрее у него точно не получится. Это первый вариант. Второй вариант, когда вы совершенно не представляете как алгоритм реализован на самом деле или просто думать не хотите, можете пойти в документации, в документации посмотреть на сложность алгоритма. Да, такой там есть, ну например, мы сравнивали ставку в начало deque и ставку в начала вектора. Давайте откроем cppreference.com, уже известный нам сайт, с документацией, и посмотрим там на push frond для deque. Тут есть пункт сложность, в котором написано - постоянная. Что означает постоянная, непонятно, мы такого не проходили, а дело всего лишь в том, что здесь у нас автоматический перевод с английской версии. Давайте, мы доросли до третьего курса, давайте перейдем на английскую версию cppreference, и вот там увидим, что сложность push front, вот у нас пункт complexity-сложность, констант. Сложность push front для deque константная, то есть О от единицы. Вставить начала deque дёшево, ну или например, мы все таки вставляли с помощью метода insert сколько работает метод insert для deque, докручиваем до сложности, вот у нас есть первый вариант, когда мы вставляем по итератору какое-то значение, вот он, первый, докручиваем до сложности первого варианта и тут написано, что сложность вставки в какой-то произвольное место deque константная плюс линейная, относительно наименьшего из расстояний между позицией, в которой мы выставляем и каким то концом контейнера. Когда мы вставляем в начало deque, расстояние до ближайшего конца deque по сути равно, но оно константное, оно равно единице, и даже нулю, поэтому сложность ставки с помощью метода insert сначала deque получается константное. Мы это поняли из документации. Если же мы тоже самое посмотрим для вектора, вектор insert вот нас интересует первая версия этого метода, смотрим на сложность и тут написано, что сложность вставки в произвольное место вектора константная плюс линейная относительно расстояния до конца контейнера. Когда мы вставляем в начало вектора, расстояние до конца контейнера линейное, поэтому и сложность получается линейной. Вот с документацией поняли, что вставлять сначала вектор менее эффективно, чем вставлять сначала deque. Хорошо, еще пример, наверно вам интересно, что будет, если вставлять в конец вектор. Наверное должна быть быстрая операция, раз мы это делали много-много раз, у нас все получалось хорошо. Вот мы открываем документацию про метод push back у вектора, докручиваем до complexity и видим, что здесь не констант, а amortized констант, амортизированная константа, это что-то интересное и об этом мы подробнее поговорим в следующих видео. Что же такое амортизированная константа, и еще я обещал рассказать про lower bound. Если мы посмотрим на сложность метода lower bound у set-а, какой она будет, она будет логарифмическим относительно размера контейнера, в общем этого и так знали. А давайте посмотрим на сложность функции lower bound, которая как раз работала медленно, будучи вызванной для set-а. Вот мы открываем документацию по функции lower bound из модулей алгоритм и смотрим на сложность. Тут написано, что lower bound совершает количество сравнений, которые пропорционально логарифму от расстояние между началом и концом, то есть сложность алгорифмическая, но, как написано в втором предложении, для итераторов, которые не является random access, для итераторов не произвольного доступа, которыми и являются на самом деле итераторы множества, для них сложность будет линейной, что у нас и получилось. Итераторы множества не random access, поэтому для них lower bound работает за линейное время, а не за логарифмическое. Мы в принципе этого могли понять, вспомнив как работает двоичный поиск. В двоичной поиске существенно, что вы берете начало, берете конец, ищете середину между ними и если [inaudible] можете к ним прибавлять произвольное число, то здесь нет проблем, это делается за константное время, это делается быстро, но если у вас итератор например, множество, вы не можете за отъединиться, прибавить к началу половину расстояния, вы даже расстояние не можете вычислить от единицы, вам нужен линейное время на то, чтобы посчитать расстояние, на то, чтобы потом прийти к середине между этими двумя итераторами, поэтому lower bound для set работает долго, используйте метод lower bound для set-а. О чем еще здесь можно поговорить? Давайте рассмотрим чуть более сложный пример, вот я сказал например, что сортировка работает за N логарифмов N, но это справедливо только для простых объектов, для чисел например. Если же у вас например, строки, тогда сортировка будет выполнять N логарифмов N не элементарных операций, а N логарифмов N в сравнении строк, и если строки длинные, тогда у вас сложность по сути умножиться на сложность сравнения строк, то есть в худшем случае на длину строки, тогда сложность сортировки будет не NlogN, а NlogN умножить на, например, длину строки в данном случае. Тоже самое будет, если вы будете искать в множестве строк или в словаре строк, вам тоже придется умножить сложность вашей операции на длину строки, потому что сравнения строк это не константная операция. Итак, мы научились примерно вычислять количество операций, которые выполняет ваша программа, в зависимости от размеров входных данных. Часто обозначаем его за N, но как же нам теперь с помощью этого сравнивать два алгоритма, или как вам зная, за сколько должен работать ваш алгоритм, например, должен успеть за 100 миллисекунд, как же вам оценить, ваш алгоритм успеет за 100 миллисекунд на конкретных данных или не успеет. Вот это мы обсудим далее.
