Luffy1
@Luffy1
Студент, Junior .NET programmer

Зачем нужно знать эффективность\сложность алгоритма?

Доброго времени суток, Хабрачане! Помогите мне, пожалуйста, ответить на этот вопрос. Я весь интернет перерыл в поисках ответа, но, в итоге, нашёл только "Что это такое?", да и сам голову ломаю уже целый день над этим вопросом. Пожалуйста, скажите, зачем это вообще нужно, зачем нужно знать, в каких ситуациях нужно знать эффективность алгоритма и как эти знания можно использовать в коде?
Для понимая: недавно начал работать с алгоритмами и часто натыкаюсь на слово "эффективность"\"сложность" в инете, хочу понять, стоит ли это учить, учитывая, что я не понимаю смысла этого и не вижу варианты использования знаний об эффективности в коде.
  • Вопрос задан
  • 236 просмотров
Решения вопроса 4
Maksclub
@Maksclub
maksfedorov.ru
Есть два алгоритма для одной задачи:
- один проходит по всем элементам один раз и что-то делает, выполняя поставленную задачу O(N)
- другой проходит по всем элементам для каждого элемента: O(N^2)

При количестве элементов N=10, в цикле в первом случае будет 10 операций, во втором случае 100 (казалось бы, в 10 раз больше всего, как и элементнов)
Но при увеличении до N=1000 в первом случае 1000 проходов, во втором уже 1 000 000 ! Видите как сильно растет разница.

Даже при небольших значениях N это может быть важно, если каждая операция долгая/тяжелая и даже 2-3х кратное увеличение может быть проблемой.
Ответ написан
firedragon
@firedragon Куратор тега C#
Senior .NET developer
Понимайте прямо. Алгоритм работает дольше. Хуже того с ростом данных его сложность возрастает, иногда линейно, а иногда по экспоненте. Ищите в интернете O и прочее. Особый привет EF и прочим ORM там это играет во все поля.

Обновил
https://tproger.ru/articles/computational-complexi...

https://ru.wikipedia.org/wiki/%D0%92%D1%80%D0%B5%D...

https://www.wisereport.ru/big-o/
https://otus.ru/nest/post/1124/
Ответ написан
ProgrammerForever
@ProgrammerForever
Учитель, автоэлектрик, программист, музыкант
Выше всё верно написали.
Вот тут есть наглядно про сложность, а также про сложность многих классических алгоритмов. Для того чтобы понять и въехать - самое то.
Ответ написан
Griboks
@Griboks Куратор тега C#
Если кратко: для вас смысла учить нет.

Если подробно...

1. Сложность/эффективность бывает разной. Обычно понимается как время выполнения или количество операций. Но также бывают и другие эффективности/сложности, например эффективность использования памяти.
2. Знание всей этой математики не даёт абсолютно никакой пользы при написании кода. Требуется оно только в двух случаях:
а) при проектировании (программным архитекторам) и только при условии жёстких ограничений (обычно слабого железа)
б) при оптимизации, когда вы просматриваете результат профилирования и видите узкое место в каком-то конкретном алгоритме
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
@mayton2019
Ent. Software engineer. Oracle. SQL. BigData.
На алгоритмической сложности стоит вся современная криптография (https-соединения в браузере) и криптовалюты. Все они сегодня работают и существуют только потому что есть алгоритмы которые работают в одну сторону легко и быстро (нанесение электронной цифровой подписи) а в обратку - настолько туго и бесконечног долго что сама по себе генерация лже-подписи становится невыгодной злоумышленнику просто по временнЫм затратам.

А если говорить простыми словами то все подмножество алгоритмов делится на константные O(1) - это поиск в хеш-табличке. Логарифмические O(Log n) - это поиск в дереве или сортированной коллекции. Линейные - любой поиск в произвольнйо коллекции O(n). И дальше идут полиномиальные (это всегда цикл в цикле) экспоненциальные O(exp n). Здесь начинается криптография. И комбинаторные, в формулу которых входит факториал от N или еще апроксимируется O(n^n). Последние как-раз и создают тот самый класс нерешаемых наукой алгоритмов для которых пытаются строить квантовые устройства работающие совсем на других физических принципах.
Ответ написан
Ваш ответ на вопрос

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

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