Расскажем просто и понятно, как определить временную и пространственную сложность алгоритмов — и зачем нужно это делать. Что такое «О» большое «О» большое (Big O notation) — это математическая нотация, которая позволяет оценить, как изменяется время выполнения алгоритма или объем используемой памяти в зависимости от размера входных данных. Есть еще «о» малое — эта нотация дает более строгую верхнюю границу для сложности алгоритма, но часто ее труднее вычислить, чем «О» большое. На практике «О» большое...

Источник: Nuances of Programming Замечали ли вы, что одни программы выполняются дольше, чем другие? Причиной задержки может быть, например, используемый компьютер. Но предположим, что у вас хороший компьютер с мощным процессором. Тогда в чем причина? Дело в том, что время выполнения написанной программы зависит от переданных входных данных. Но как выяснить, эффективна ли программа? Есть ли способ это определить? Как проверить, при передаче каких входных данных программа работает лучше всего? Прежде чем перейти к ответам, разберемся с тем, как вообще работает эффективная программа...