Для любого практического применения log(n) можно считать константой. Просто в некоторых компаниях эта константа больше, чем у вас. © народная мудрость

Половину жизни я учу программировать. В том числе учу разработчиков делать быструю оценку вычислительной сложности алгоритма. Зачем?!

На первый взгляд, это довольно академический навык, который не нужен за рамками экзамена по алгоритмам. Однако опытные разработчики используют его ежедневно, не задумываясь, на уровне рефлексов. Делают они это для грубого анализа кода, который читают, пишут или только собираются написать. Обычно быстрого анализа асимптотики достаточно, чтобы исключить случайное появление сильно неэффективного кода.

Сначала разберёмся, как делать оценку сложности, на примере короткой, но нетривиальной задачи. Потом я расскажу, как научится делать экспресс-оценку, и покажу статистику о том, как решали задачу-пример участники конференций Joker и DotNext.

Читать дальше ->

https://habrahabr.ru/post/348870/