Всегда была тяжелая тема по алгоритмам, их сложность и тд. Даже написание кода по какому-то определенному алгоритму - вызывали холодный пот)
Меня интересует, как в коде понять сложность алгоритма? Окэй, по поводу n^3 => три цикла; n^2 - два цикла. А как быть с сложностями типу: nlogn? logn?log(m+n)?
Так же интересует, к примеру, на код-интервью кандидата просят решить задачу, он ее решает худо-бедна, и спрашиваю какая сложность ее? как ее можно усовершенствовать?
Окэй, понимаю если там, к примеру, если задача была решена глупой сортирвкой(n^3), и ее можно усовершенствовать как минимум баблом(n^2). А как быть когда это nlogn или другие вариации?
Очень грубо говоря, n log n означает, что у нас цикл двойной вложенности, но за счёт правильной организации алгоритма длительность вложенных циклов становится заметно меньше, чем n.
Понимать сложность алгоритмов - сложно. В общем случае глядя на исходних достаточно трудно сказать какое там o(n). Особенно если есть рекурсии и предикаты которые срабатывают с вероятностью которую мы не знаем.
Вообще, нарабатывая опыт. Например обход элементов квадратной матрицы имеет квадратичную стоимость а обход куба - кубическую. Это из простого. Шаблоны дихотомического поиска почти всегда содержат в основе своей формулы логарифм по основанию 2. И комбинаторные алгоритмы (сочетания и перестановки) - практически всегда содержат в своей основе n под факториалом.
Кстати если формула содержит суперпозицию факториала и полинома - то полином можно выкинуть. Т.к. в сравнении пределов факториал улетает в бесконечность быстрее и соотв. решение зависит только от факториала.
Я не очень понимаю зачем для собеседования знать оценку неизвестных алгоримов. Я прошел не один десяток интервью и меня никогда никто не просил оценить сложность неизвестного алгоритма.
По поводу Дональда Кнута. Ничего он не поймет. Кнут писал 40 лет назад. Писал про железо которого уже не существует (ленточные накопители) и продавливал свои идеи алгоритмизации на ограниченном числе ресурсов. Кнут просто издевается над современным читателем имеющим ноутбук и смартфон тем фактом что заставляет изучать несуществующий компьютер MMIX (это такая себе машинка-калькулятор вроде Феликса или Энигмы, такие вот у меня ассоциации) и под него-же писать и читать код. Ну кому это надо!
Сегодня я снимаю шляпу перед тем трудом который он сотворил. Но если студент хочет ПРОСТО освоить тему оценок сложностей алгоритмов то можно взять что-то более быстрое и эффективное. Вирт. Седжвик. Даже Кормен.
Так или иначе придется считать количество операций. Иногда это просто, когда там тупо вложенные циклы с фиксированным количеством итераций. Иногда придется пораскинуть мозгами. Например, можно понять сколько уровней будет у рекурсивного вызова и как много операций на каждом уровне происходит. Логарифмы обычно вылезают от деления данных пополам. Когда просят сделать что-то быстрее то надо подумать а нельзя ли тут применить какую-то структуру данных. Например, можно ли BST заменить хеш таблицей.
P.S. Простого ответа нет. Никто не говорил, что будет легко. Даже есть поговорка: тяжело в учении - легко в бою. Ну а если в учении легко, то в бою - верная смерть.
