Комментарии 7
Было бы полезным указать случаи, при которых O(n) может быть хуже, чем O(n^2), так как значение n в зависимости от алгоритма бывает разным
Картинка неправильная. O(1) - это телепортация.
Ни о чём статья. Таких я видел уже дофига, но вот почему-то до сути не доходит никто. У меня есть знакомый, дал я как-то ему задачу на префиксные суммы - научиться быстро вычислять суммы на подотрезках массива, если к массиву не делаются запросы на модификацию. Он написал на каждый запрос лобовое суммирование за линию. Я говорю ему, что надо бы побыстрее, так он стал в цикле в сумму докидывать сразу i'ый и N-i'ый элементы, мол, O(n/2). К чему я это - тема алгоритмической сложности довольно неочевидна, тут ботать надо плотно. Ни разу в научпопе не видел, чтобы объясняли, почему мы не пишем константы.
Кстати, о константах. Автор, вы бы как предпочли проверять на простоту: "до корня", т.е. за экспоненту, или за O(N^6)? Алгоритм АКС как раз за полином работает, берём его?
Надо не забывать еще, что в реальной жизни кроме асимптотического приближения есть еще и коэффициент. И алгоритмы с хорошей асимптотой имеют тенденцию обладать большим коэффициентом. И поэтому могут проигрывать простым алгоритмам, когда данных мало.
Очень хорошее объяснение! Понравилось, что сначала показан реальный пример с измерением времени, а потом плавно подвёл к О-большому. Это помогает понять, зачем вообще нужна асимптотическая оценка. Единственное, что можно добавить — что Big O описывает лишь порядок роста, но константы тоже играют роль. Иногда алгоритм с худшей асимптотикой может оказаться быстрее на малых входных данных, и это тоже важно учитывать в реальной разработке.
Сложность алгоритмов, или почему O(n) лучше O(2^n)