Как понять в коде сложность алгоритма?

Всегда была тяжелая тема по алгоритмам, их сложность и тд. Даже написание кода по какому-то определенному алгоритму - вызывали холодный пот)

Меня интересует, как в коде понять сложность алгоритма? Окэй, по поводу n^3 => три цикла; n^2 - два цикла. А как быть с сложностями типу: nlogn? logn?log(m+n)?

Так же интересует, к примеру, на код-интервью кандидата просят решить задачу, он ее решает худо-бедна, и спрашиваю какая сложность ее? как ее можно усовершенствовать?

Окэй, понимаю если там, к примеру, если задача была решена глупой сортирвкой(n^3), и ее можно усовершенствовать как минимум баблом(n^2). А как быть когда это nlogn или другие вариации?
  • Вопрос задан
  • 430 просмотров
Решения вопроса 1
@mayton2019
Bigdata Engineer
Понимать сложность алгоритмов - сложно. В общем случае глядя на исходних достаточно трудно сказать какое там o(n). Особенно если есть рекурсии и предикаты которые срабатывают с вероятностью которую мы не знаем.

Вообще, нарабатывая опыт. Например обход элементов квадратной матрицы имеет квадратичную стоимость а обход куба - кубическую. Это из простого. Шаблоны дихотомического поиска почти всегда содержат в основе своей формулы логарифм по основанию 2. И комбинаторные алгоритмы (сочетания и перестановки) - практически всегда содержат в своей основе n под факториалом.

Кстати если формула содержит суперпозицию факториала и полинома - то полином можно выкинуть. Т.к. в сравнении пределов факториал улетает в бесконечность быстрее и соотв. решение зависит только от факториала.

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

По поводу Дональда Кнута. Ничего он не поймет. Кнут писал 40 лет назад. Писал про железо которого уже не существует (ленточные накопители) и продавливал свои идеи алгоритмизации на ограниченном числе ресурсов. Кнут просто издевается над современным читателем имеющим ноутбук и смартфон тем фактом что заставляет изучать несуществующий компьютер MMIX (это такая себе машинка-калькулятор вроде Феликса или Энигмы, такие вот у меня ассоциации) и под него-же писать и читать код. Ну кому это надо!

Сегодня я снимаю шляпу перед тем трудом который он сотворил. Но если студент хочет ПРОСТО освоить тему оценок сложностей алгоритмов то можно взять что-то более быстрое и эффективное. Вирт. Седжвик. Даже Кормен.
Ответ написан
Комментировать
Пригласить эксперта
Ответы на вопрос 4
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Так или иначе придется считать количество операций. Иногда это просто, когда там тупо вложенные циклы с фиксированным количеством итераций. Иногда придется пораскинуть мозгами. Например, можно понять сколько уровней будет у рекурсивного вызова и как много операций на каждом уровне происходит. Логарифмы обычно вылезают от деления данных пополам. Когда просят сделать что-то быстрее то надо подумать а нельзя ли тут применить какую-то структуру данных. Например, можно ли BST заменить хеш таблицей.
Ответ написан
Комментировать
dollar
@dollar
Делай добро и бросай его в воду.
Мат. анализ и практика программирования помогают в этом. Да, это большие области знаний.

Кратко можно ознакомиться здесь:
https://ru.wikipedia.org/wiki/«O»_большое_и_«o»_малое

P.S. Простого ответа нет. Никто не говорил, что будет легко. Даже есть поговорка: тяжело в учении - легко в бою. Ну а если в учении легко, то в бою - верная смерть.
Ответ написан
Комментировать
Griboks
@Griboks
Всё очень просто. Запускаете бенчмарк - получаете сложность. Если просят оценить в уме, то оцениваете по самому низкопроизводительному участку кода.
Ответ написан
Комментировать
AgentSmith
@AgentSmith
Это мой ответ на твой вопрос
Почитай Дональда Кнута и всё поймёшь. Не зря же это классика для программистов.
logn - это поиск элемента в hashmap
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы