Комментарии 17
while (left <= right)
Опечаточка
В общем, данные довольно известные, но за "Сложность встроенных методов JavaScript" спасибо
Спасибо, освежил память! Просто как рекомендация – когда читал, то не хватало графиков для наглядности в каждом типе сложности, пока читаешь. Только потом увидел, что все вместе есть дальше
Здравствуйте. Сделаю маленькое замечание или, скорее, пожелание. Примеры у вас очень академические. Факториал, например. Если на лекции спросить: Заказчик требует перебрать все циклы в графе, близком к полному. Какова выч. сложность этой задачи? Сразу ответят "n квадрат". Про перестановки все знают, а что гамильтонов цикл тоже перестановка - не догадываются. Лучше бы иллюстрировать такую сложность модельными трудно решаемыми задачами.
Наглядно подано, потому будет понятно даже новичку, только ошибка в нативных методах добавления / удаления в / из массив(а) и их сложности.
Но даже если вы думаете, что никогда не будете этим пользоваться, стоит ознакомиться как минимум для собеседований ;)
Половину абзацев можно было бы заменить формальным определением:
Алгоритм со временем работы
T(n)имеет сложность ("порядок", или "степень роста")O(f(n))если: существуют такие положительные константыCиN, что для всехn > NT(n) < Cf(n)
Это, конечно, хорошо, что приведена куча примеров, где все буквально "на пальцах", но коль уж такая серьезная (хотя бы даже по объему) статья, можно было бы хоть чуть-чуть и формализма.
DEL!
А в какую категорию сложности входит алгоритм, выполняющийся за время O(n (log n)^2) ? У меня реально такая задача есть, реализованная в программе.
Выше @nronnieпривёл формальное определение O-нотации, из которого видно, что время работы T(n) может одновременно относиться к нескольким разным функциям f(n), если соблюдаются упомянутые условия. Так, если T(n) = O(n), то всегда можно сказать, что T(n) = O(n^2), хотя и бесполезно. Аналогично, если T(n) = O(n (log n)^2), то T(n) = O(n sqrt(n)).
В сущности, вопрос может быть сведён к тому, насколько точную оценку мы хотим предоставить в O-нотации. Если мы хотим сказать «ну, время растёт быстрее n log n, но всяко медленнее n sqrt(n)», то пишем O(n sqrt(n)). Если хотим сказать «время растут не быстрее n (log n)^2 и это хорошая оценка», то пишем O(n (log n)^2). Собственное имя есть не у каждого класса функция (что очевидно, ведь имён конечное количество, а классов функций несчётно много).
let mid = Math.floor((left + right) / 2);
Конечно, сегодня максимальная длина массива в JS ограничена 2^32-1, что гораздо меньше Number.MAX_SAFE_INTEGER, но лучше считать средний индекс безопасным, с точки зрения переполнения, способом.
Хорошая статья, написано все, что надо для того, чтобы пересылать ее знакомым.
В примерах, где используются производные индексы от arr.length (первый - printTwice), хорошо бы в теле цикла использовать не arr[i], а i. Выход за границы массива заставляет сжиматься моё...
Последнее предложение в умножении матриц грамматически не.
Отличная статья! Жаль, не могу поставить плюс.
Но есть и спорный момент - про тот же интернет-магазин, который рассматривается в самом начале. Что-то не вспомню ни одного программиста, который бы вместо технологий использовал бы алгоритмы.
Поясню. Вот у нас интернет-магазин. А вот у нас программист. Он хочет сделать поиск по товарам, которые лежат в базе данных, которую уж точно написал не этот программист - он просто использует СУБД. Т.е. программист использует технологию. Одну из. И если проект чуть больше ларька (а уж ларьки - и тем более - они юзают какой-нить готовый интернет-магазин), то и программистов несколько - бэкэндеры, фронтэндеры, фуллстэккеры, ... И вот бэкэндэру надо вывалить список товаров по запросу с фронта. И бэкэндер идет куда? Нет, не к книжкам Кнута, а к интернетам, гед он вводит запрос о том, как реализовать поиск. И он видит все эти эластиксерчи, все эти полнотекстовые индексы, а потом читает статьи на хабре, где бравые ребята с продаванов курсов рассказывают, что нужно использовать лимит (часто без сортировки), "чтобы было быстрее". Ну да, без сортировки будет быстро, только в выводе будет что угодно первое (например, я как-то на авито искал корову, но первые три страницы были бычки и телочки, которые не дают молока). Т.е. что делает программист, которому нужно поискать? Ищет технологию, а не алгоритм, с помощью которого э\ту технологию можно нарисовать самостоятельно.
И я вот всеми тремя руками за то, чтобы программист знал алгоритмы, чтобы он если что и лимитит, то чтобы упорядочивал, ну и чтобы понимал, что если он что-то упорядочивает, то даже первые условно десять вызовут перебор всех элементов, т.к. поиск максимального значения только на квантовых компьютерах имеет сложность О(sqrt(N)), а на обычных компьютерах - O(N).
поиск максимального значения только на квантовых компьютерах имеет сложность О(sqrt(N)), а на обычных компьютерах - O(N).
Если есть индекс по полю, то поиск max() будет уже не O(N), а меньше (индекс с балансированным деревом даст, к примеру, O(log(N)))
Ровно так. Даже круче, ибо мах/мин по индексу - это первый/последний, т.е. О(1).
Но если у вас есть поле с каким-то текстом, и Вы этот текст ищите в каком-то поле вашей СУБД (ну или в полнотекстовом индексе), и при этом Вам нужно получить, например, 10 самых релевантных записей, то какое будет тут О? На сколько я знаю, полнотекстовый поиск хранит все "слова" в виде "слово": [запись1, запись2, ...]. В итоге мы получим все записи с нужными нам словами за некое О(Лог2Н), ну или по хеш-таблице за еще может быть быстрее, а дальше нам нужно найти первые 10 из них, которые будут самыми релевантными. Т.е. это еще какое-то О(Х). А потом я получаю телок и быков вместо коровы на первых трех страницах. И когда я пишу "Корова" -"бык" -"телка", то только после этого получаю нужное мне. И тут еще какое-то О(Х).
Но если у нас есть какая-то функция, которая для поля найдет некий коэффициент К степени релевантности записи к запросу, то если нам нужно будет найти все записи, у которых этот коэффициент больше 0,4, например, то какова у нас тут будет эффективность? А ведь многие полнотекстовые индексы работают именно так.
Но я все-же больше о том, что когда кто-то начинает пользоваться инструментом, неплохо было бы этому кому-то понимать, как работает инструмент. Но, как показывает практика, иногда даже в больших проектах с этим не разбираются, ибо "гугл найдет".
что-то не припомню я разделяйку за O(2^n). за O(n * log(n)) только в сортировке слиянием и в бпф
Сложность алгоритмов. Разбор Big O