Почему алгоритм, работающий за O(n), может быть медленнее алгоритма, работающего за O(n^2), при малых значениях n?
Однозначного ответа на вопрос, какой алгоритм будет быстрее при малых значениях n, нет. 3
Это связано с тем, что при малом количестве действий важнее становится время выполнения отдельных операций. 1 Например, если сравнивать квадратичный и линейный алгоритмы при n = 10, то квадратичный сделает примерно 100 действий, линейный — примерно 10. 1 Но может оказаться, что в линейном алгоритме каждая операция работает в 10 раз дольше, и поэтому время выполнения будет одинаковым. 1
Кроме того, одна итерация второго алгоритма может оказаться быстрее, чем одна итерация первого, и тогда второй алгоритм может оказаться быстрее. 3 Но рано или поздно найдётся такое число n, при котором даже быстрых итераций второго алгоритма окажется слишком много, и первый алгоритм окажется быстрее. 3
Таким образом, при сравнении алгоритмов важно учитывать не только сложность, но и другие факторы, влияющие на скорость выполнения. 3
