Зачем нужно знать эффективность\сложность алгоритма?
Доброго времени суток, Хабрачане! Помогите мне, пожалуйста, ответить на этот вопрос. Я весь интернет перерыл в поисках ответа, но, в итоге, нашёл только "Что это такое?", да и сам голову ломаю уже целый день над этим вопросом. Пожалуйста, скажите, зачем это вообще нужно, зачем нужно знать, в каких ситуациях нужно знать эффективность алгоритма и как эти знания можно использовать в коде?
Для понимая: недавно начал работать с алгоритмами и часто натыкаюсь на слово "эффективность"\"сложность" в инете, хочу понять, стоит ли это учить, учитывая, что я не понимаю смысла этого и не вижу варианты использования знаний об эффективности в коде.
Сложность алгоритма позволяет вычислить и заранее предположить количество времени или процессорной мощности, которая потребуется чтобы обработать какой-то количество запросов.
Следовательно, зная для чего кого этот алгоритм пишется, можно понять справится ли он с нагрузкой, или нужно искать другой, или другого алгоритма нет, и нужно посчитать насколько мощный сервер нужен для того, чтобы все работало с приемлимой скоростью.
Есть два алгоритма для одной задачи:
- один проходит по всем элементам один раз и что-то делает, выполняя поставленную задачу O(N)
- другой проходит по всем элементам для каждого элемента: O(N^2)
При количестве элементов N=10, в цикле в первом случае будет 10 операций, во втором случае 100 (казалось бы, в 10 раз больше всего, как и элементнов)
Но при увеличении до N=1000 в первом случае 1000 проходов, во втором уже 1 000 000 ! Видите как сильно растет разница.
Даже при небольших значениях N это может быть важно, если каждая операция долгая/тяжелая и даже 2-3х кратное увеличение может быть проблемой.
Понимайте прямо. Алгоритм работает дольше. Хуже того с ростом данных его сложность возрастает, иногда линейно, а иногда по экспоненте. Ищите в интернете O и прочее. Особый привет EF и прочим ORM там это играет во все поля.
То есть это нужно для того, чтобы в какой-то ситуации можно было сравнить два алгоритма по эффективности и выбрать лучший вариант для конкретной ситуации?
Денис Бредун, это нужно, чтобы понимать, что на некоторых данных твоя программа работает мгновенно,а на некоторых - вечность. И разница между данными не так уж высока.
какая вообще связь между стрингбилдером и сложностью алгоритма?
А вы сравните
[Fact]
public void SbVsConcatTest()
{
const int size = 60 * 1000;
var s = string.Empty;
var concatStart = DateTime.Now;
for (var i = 0; i < size; i++) s += i;
var concatEnd = DateTime.Now;
var sb = new StringBuilder();
var sbStart = DateTime.Now;
for (var i = 0; i < size; i++) sb.Append(i);
var sbEnd = DateTime.Now;
Debug.WriteLine($"concat: {(concatEnd - concatStart).TotalMilliseconds}");
Debug.WriteLine($"sb: {(sbEnd - sbStart).TotalMilliseconds}");
}
Владимир Коротенко, хотелось бы заметить, что происходит значительная просадка в памяти
При изменении значения StringBuilder размер не перераспределяется, если не достигнута максимальная емкость. Когда это происходит, новое пространство выделяется автоматически, а емкость удваивается.
Выше всё верно написали. Вот тут есть наглядно про сложность, а также про сложность многих классических алгоритмов. Для того чтобы понять и въехать - самое то.
1. Сложность/эффективность бывает разной. Обычно понимается как время выполнения или количество операций. Но также бывают и другие эффективности/сложности, например эффективность использования памяти.
2. Знание всей этой математики не даёт абсолютно никакой пользы при написании кода. Требуется оно только в двух случаях:
а) при проектировании (программным архитекторам) и только при условии жёстких ограничений (обычно слабого железа)
б) при оптимизации, когда вы просматриваете результат профилирования и видите узкое место в каком-то конкретном алгоритме
На алгоритмической сложности стоит вся современная криптография (https-соединения в браузере) и криптовалюты. Все они сегодня работают и существуют только потому что есть алгоритмы которые работают в одну сторону легко и быстро (нанесение электронной цифровой подписи) а в обратку - настолько туго и бесконечног долго что сама по себе генерация лже-подписи становится невыгодной злоумышленнику просто по временнЫм затратам.
А если говорить простыми словами то все подмножество алгоритмов делится на константные O(1) - это поиск в хеш-табличке. Логарифмические O(Log n) - это поиск в дереве или сортированной коллекции. Линейные - любой поиск в произвольнйо коллекции O(n). И дальше идут полиномиальные (это всегда цикл в цикле) экспоненциальные O(exp n). Здесь начинается криптография. И комбинаторные, в формулу которых входит факториал от N или еще апроксимируется O(n^n). Последние как-раз и создают тот самый класс нерешаемых наукой алгоритмов для которых пытаются строить квантовые устройства работающие совсем на других физических принципах.
