[БЕЗ_ЗВУКА] Первое, чему
нам сейчас нужно научиться, это сравнивать два алгоритма, зная их сложность.
И здесь, в общем-то, все понятно.
У нас бывает, ну,
на примере [НЕРАЗБОРЧИВО] — у нас была сложность логарифма, была сложность N.
Конечно, N больше, чем логарифм N, особенно когда N достаточно велико.
В целом здесь, опять же, математика чуть посложнее, чем сложение и умножение,
но все еще простая математика.
Если у алгоритма сложность с логарифмом N это больше, чем константная сложность.
Если у логарифма линейная сложность, у такого алгоритма сложность будет больше,
чем у алгоритма с логарифмической сложностью.
И так далее.
N больше чем логарифм N.
NlogN больше чем N.
N квадрат больше чем NlogN, и так далее.
Несложная математика, когда вы знаете сложность алгоритмов,
вы можете легко их сравнить — какой из них будет более эффективный чем другой.
Здесь, правда, есть небольшой ньюанс.
Когда мы оцениваем сложность, мы там местами ее складывали.
Например, у нас получалось логарифм N плюс 1.
Вот это 1 оно в целом здесь не очень интересно, потому что оно меньше,
чем логарифмы.
По сути логарифм N+1 это примерно то же самое что и логарифм.
То есть при сложении двух сложностей вы можете применять правило поглощения.
Именно поглощать меньшую сложность большей сложностью.
Например, N плюс логарифм N это примерно то же самое что N.
Раз мы констанут игнорируем, то и такие меньшие сложности тоже можно игнорировать.
Конечно, если у вас вдруг получилось два алгоритма с линейной сложностью,
O(N) и O(N), то константу все равно нужно игнорировать,
и 5N и 8N вы с помощью описанного нами метода не сравните.
В таких случаях,
когда сложность получилось с точностью до константы одинаковой,
вам нужно честно брать, программировать и сравнивать на ваших данных.
Здесь такой грубый анализ не поможет.
Более того, даже если вы сравниваете алгоритмы, у которых сложность
вроде бы отличается содержательно, например N и NlogN, вы должны примерно
понимать насколько велика ваша константа, которую вы проигнорировали.
Например, когда у вас задачи геометрические или когда вы вообще
программируете какие-нибудь видеоигры, в этом случае константа может быть
настолько велика, что весь этот анализ можно выкинуть в помойку.
Вам все равно нужно программировать, думать, замерять.
Есть вполне реальный пример когда в двух разных видеоиграх один разработчик
построил какое-то бинарное дерево поиска, которое работало за логарифм,
все там оптимизировал,
а другой просто подумал головой и как-то аккуратно написал там линейные поиски.
И вот сложность с линейными поисками была меньше в итоге, то есть такая игра
работала эффективнее, чем игра в которой было какое-то дерево поиска.
Пожалуйста, думайте про константу и замеряйте все-таки производительность
вашего алгоритма в сложных случаях.
Все-таки, как нам примерно оценить
подходит ли конкретный алгоритм под заданные ограничения?
Представьте, что вы знаете, что ваш алгоритм должен уложиться в одну секунду.
И ему на вход подается массив из N элементов.
Как вам оценить, подойдет ли конкретный алгоритм,
или нужно брать алгоритм более эффективный?
Итак, вы рассматриваете худший случай.
Вы берете сложность вашего алгоритма и в качестве N или каких-то других
параметров подставляете туда максимальные значения наших выходных данных.
Например, у вас был алгоритм сложностью NlogN, вы знаете, что N — максимум 100
000, ну и прямо вычисляете: 100 000 умножить на логарифм от 100 000.
У вас получается какое-то количество операций вашего алгоритма.
Далее нужно вспомнить, что мы игнорировали константу и примерно прикинуть, насколько
велика константа в вашем алгоритме, насколько у вас сложные операции.
Либо вы просто N раз делаете ++ какую-то переменную (тогда это простая операция),
либо вы вычисляете квадратный корень и что-то еще сложное делаете.
В зависимости от этого полученное количество операций нужно умножить на
какую-то константу, скажем, 10 или 50, примерно в этом диапазоне.
Вы получаете количество элементарных операций, очень грубо, которое, конечно,
зависит от процессора, от компилятора, от реализации стандартных алгоритмов,
но тем не менее, вы грубо оцениваете количество простейших операций и дальше
прикидываете за сколько этот алгоритм будет работать исходя из того, что
за секунду на хороших процессорах можно успеть сделать миллиард простых операций.
Еще раз.
Если у вас была сложность NlogN, вы поставили туда максимальное значение N,
перемножили, посчитали, умножили на константу и получили 10 в 8,
10 в 9, вы успеете за секунду, все будет хорошо.
Хотя все равно, пожалуйста, поставьте максимальные входные данные перед
отправкой в систему и проверьте, что вы успеваете за секунду.
Так вы будете гораздо больше уверены в том, что все будет хорошо.
Давайте пожалуйста теперь рассмотрим на примерах
из прошлых курсов какая получалась сложность алгоритма.
Первый пример — задачи синонимы из белого пояса.
Что там нужно было делать?
Вам поступали запросы трех типов.
Запрос первого типа — добавить пару слов сказать, что это синонимы.
Слова word1 и word2.
Запрос второго типа — посчитать количество синонимов конкретного слова.
Запрос третьего типа — проверить, являются ли два слова синонимами.
При этом мы в прошлых курсах вам явно не говорили, что у вас может быть максимум
столько-то запросов, вы должны успеть за столько-то секунд.
Сейчас мы будем честнее, благо вы теперь научились оценивать сложность,
и теперь мы раскроем вам секрет.
В той задаче первого курса вам приходило максимум 70 000 запросов,
вы должны были успеть обработать их за одну секунду.
И что важно, слова имеют длину не больше чем 100.
Давайте, вооруживший этим знанием, посмотрим решение,
опубликованное нами в задаче "синонимы" и посмотрим, сколько же оно будет работать.
Итак, вот у нас функция main.
Здесь мы создаем, напоминаю, словарь множеств.
Мы для каждого слова будем запоминать множество его синонимов.
Теперь обрабатываем каждый запрос.
Запросов у нас q.
У этого цикла будет, соответственно, q итераций.
Здесь будет q итераций.
Здесь мы считываем операцию и в зависимости от типа операции
что-то делаем.
Если это операция ADD, мы считываем два слова.
Кстати, какова сложность операции считывания двух слов?
Если мы скажем, что слово имеет длину не более чем l, тогда мы считаем два
слова длины не более чем l за l простейших операций.
Дальше мы хотим обратиться к ключу словаря по первому слова,
и вставить в соответствующее множество второе слово, и наоборот.
Давайте оценивать.
Поиск в словаре конкретного ключа работает за логарифм от размера этого словаря.
Размер этого словаря в худшем случае будет равен количеству слов,
которе мы туда уже вставили, то есть количеству запросов.
Соответственно, здесь у нас получается, логарифм от количества
запросов умножить на стоимость сравнения двух строк длины не более чем l.
То есть l логарифмов q.
Мы получили соответствующее множество и теперь в него вставляем.
Сложность вставки в это множество будет такой же.
У нас множество имеет размер в худшем случае q, соответственно,
вставка в него будет за логарифмом q, плюс надо будет умножить на сложность
сравнения двух строк, опять же, l логарифмов Q.
Соответственно вот здесь l логарифмов Q и здесь тоже l логарифмов Q.
Итого, сложность обработки запроса ADD у нас получается l + l logQ.
Поглощаем первое вторым,
и получаем сложность O(LlogQ).
Теперь смотрим на COUNT.
Тут, в общем-то, все то же самое.
Мы считали слово длина которого не более чем l,
нашли его в словаре и получили размер этого множетсва.
Поиск в словаре будет занимать LlogQ.
То есть тут то же самое.
И, наконец, операция CHECK, в которой мы делаем по сложности примерно то же самое.
Мы здесь считываем два слова длиной более чем L,
ищем их в словаре и потом во множестве.
Это тоже LlogQ.
[БЕЗ_ЗВУКА] Итого
каждый запрос мы обрабатываем за L логарифмов Q.
Всего у нас Q запросов, поэтому суммарная сложность этой программы
получается O от q умножить на L, умножить на logQ.
Если у нас 100 000 запросов, например,
тогда как нам проверить за сколько секунд мы успеем обработать все эти запросы?
Мы берем 100 000, умножаем на длину строки, которая у нас до 100,
получаем уже 10 в 7 степени, и умножаем на логарифм от 100 000.
Это меньше чем 20 даже.
Итого у нас получается 20 умножить на 10 в 7 степени — 2 на 10 в 8.
И столько простых операций мы вполне себе успеем сделать за секунду,
поэтому вот такой алгоритм в систему можно задать.
Собственно, поэтому мы его и опубликовали.
Но если вы напишет менее оптимальное решение (попробуйте в качестве
небольшого упражнения, если вы не спешно задавали что-то в систему на первом
курсе и превышали лимит по времени, попробуйте посмотреть на то решение и
оценить его сложность), скорее всего в каком-то из запросов, например, CHECK,
вы увидите какой-нибудь лишний цикл, который будет увеличить сложность
сложность обработки этого запроса с LLogQ до чего-нибудь более страшного.
Например, Q умножить на L.
И тогда вы, конечно, успевать в секунду не будете.
Хорошо, смотрим ещё одну задачу.
Тоже из первого курса, из раздела про объектно-ориентированное программирование,
про классы.
И задача «Имена и фамилии — 1».
В этой задаче что нужно было делать?
Нужно было добавлять разные записи в историю.
Запись о том, что у человека изменилось имя в такой-то год на такое-то значение.
Что у человека изменилась фамилия в такой-то год на такое-то значение.
И для конкретного года говорить на этот момент, на этот год,
какие у человека имя и фамилия.
Здесь были довольно лояльные ограничения: 100 запросов,
слова длины 10 и целая секунда в вашем распоряжении.
Но, тем не менее, давайте оценим сложность.
Откроем опубликованное нами решение по этой задаче и посмотрим на него.
Вот класс Person.
Два очень похожих метода ChangeFirstName и ChangeLastName.
За какую сложность они работают?
Здесь мы берём число year, ищем это число
как ключ в словаре, и на это мы тратим сколько операций?
Логарифм от размера этого словаря.
Размер словаря в худшем случае будет равен количеству запросов,
то есть логарифм Q.
Ну и плюс мы ещё туда сохраняем нашу строчку.
На это тратим ещё L операций.
Тут лучше ничего не поглощать, у вас совершенно разные величины L и логарифм Q.
Можем в таком виде прямо оставить сложность: L плюс логарифм Q.
Такая же сложность у метода ChangeLastName: L плюс логарифм Q.
И, наконец, нам интересен метод GetFullName, сколько же он будет работать?
Здесь интереснее.
Здесь мы дважды вызываем функцию FindNameByYear,
сложность которой мы пока не оценили, но нам придётся это сделать.
А вот всё остальное, что делается после вызова функции FindNameByYear,
тут кажется всё довольно просто.
Мы смотрим только на пустоту строки, которую мы оттуда получили: if, if,
ну и складываем строчки.
То есть сложность того, что у нас здесь после, получается O от L,
которая тратится на сложение строк длины максимум L.
А вот сложность функции FindNameByYear гораздо интереснее.
Давайте на неё посмотрим.
Она принимает словарь, принимает год и ищет год в этом словаре.
По сути она ищет первую запись, точнее, последнюю запись,
в которой год меньше либо равен данному.
И в первом курсе мы ещё не знали про lower bound,
поэтому здесь это делается циклом for.
Цикл for делает столько операций, сколько у нас записей в истории, в худшем случае.
То есть итерацией здесь будет O от Q,
и каждая итерация сравнивает года.
Это O от единицы, сравнить два числа это легко.
А вот присвоить одну строчку в другую требует столько операций,
какова длина строки.
По сути мы копируем одну строчку в другую.
Итого у нас получается сколько операций?
Сложность одной итерации цикла for — L, всего Q итераций,
итого O от QL операций мы тратим на один вывод функции FindNameByYear.
Соответственно, сложность метода GetFullName увеличивается
ещё на эти самые O от QL.
Конечно, второе слагаемое больше, чем первое,
поэтому можем просто написать O от QL.
Итого сложность этих запросов O от L плюс OQ.
А сложность этого запроса O от QL.
Понятно, что это самый тяжёлый запрос,
и именно из-за него ваша программа работать будет медленно.
Но в рамках первого курса мы получали сложность одного и всех запросов
O от Q умножить на сложность одного запроса.
Что больше — QL или LogQ плюс L?
Конечно, QL больше, чем LogQ плюс L.
Поэтому давайте считать, что один запрос имеет в худшем случае сложность QL.
Итого у нас получается Q в квадрате умножить на L.
Конечно, если у вас всего тысяча запросов
и строки длины даже до 100, вы всё равно прекрасно успеете за одну секунду.
Но если вести разговор о том, как нам оптимизировать этот код,
нужно оптимизировать то его место, которое имеет наибольшую сложность.
Вот методы change, они работают быстро, в общем-то, тут всего лишь L и логарифм Q.
А метод GetFullName работает долго,
поэтому именно его нужно оптимизировать в первую очередь.
Даже, если говорить точнее, нужно оптимизировать функцию FindNameByYear.
И действительно, на втором курсе мы просили вас оптимизировать этот код,
и что же получилось?
Я напомню, что это была задача «Имена и фамилии — 4».
Мы нашли узкое место этого решения.
И давайте посмотрим на оптимизированное решение и прикинем,
сколько запросов в секунду оно может обработать.
Итак, решением задачи «Имена и фамилии — 4», конечно же, опубликованное нами.
Здесь те же самые методы ChangeFirstName и ChangeLastName,
которые работают за
L плюс LogQ.
И функция FindNameByYear нам интересна больше всего,
и в ней теперь выполняется, называется, метод upper_bound,
который работает за логарифм от размера контейнера, то есть за логарифм Q.
Итого вот эта функция работает за логарифм Q,
за логарифм размера словаря Names.
Плюс нам тут надо скопировать самим два итератора, это легко,
плюс надо скопировать вот эту строчку вот в эту плюс L.
Итого мы получаем, что и третий метод нашего класса работает быстро,
то есть LogQ плюс L, столько же, сколько и первые два метода.
Итого каждый запрос работает за LogQ плюс L.
И мы получаем суммарную сложность Q умножить на L плюс LogQ.
Почему у нас логарифм не понадобилось умножать на L?
Потому что мы ищем в словаре чисел, а не строк.
Сравнение чисел имеет константную сложность.
Ну и теперь давайте прикинем,
при каком Q мы успеем обработать все эти запросы за одну секунду.
Скажем, если Q — миллион, тогда у нас будет миллион умножиться
на длину строки, кажется, десять, плюс логарифм от миллиона, это двадцать.
Миллион умножаем на тридцать, грубо говоря, и получаем тридцать миллионов,
прекрасно успеваем за секунду.
Наверное, даже если запросов будет миллионов пять,
мы всё равно успеем за секунду.
Итак, мы прошлись по разным примерам.
И теперь мы умеем понимать,
успеет ли написанный нами алгоритм в конкретное ограничение по времени.
В частности, в наших задачах вам это умение нужно будет продемонстрировать.
Вам будет дано ограничение по времени — обычно одна секунда,
ограничение на данные, которые будут вами вводится — например, 100 000 чисел.
И вам нужно будет написать алгоритм, который будет адекватен этим ограничениям,
которые будет в худшем случае проходить заданные нами ограничения по времени.
