Как сравнивать функции по времени выполнения и Big-O

Задача на оценку эффективности: расположить три функции по времени выполнения

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

Подробный ответ

Условие задачи

Расположите функции по возрастанию времени выполнения при больших значениях n:

f1(n) = 3 * n + 100
f2(n) = n * log2(n)
f3(n) = n ** 2

Шаг 1. Упростить Big-O

f1(n) = 3n + 100 имеет сложность O(n);
f2(n) = n log n имеет сложность O(n log n);
f3(n) = n² имеет сложность O(n²).

Шаг 2. Сравнить рост

При достаточно больших n линейная функция растёт медленнее, чем n log n, а n log n растёт медленнее квадратичной функции.

O(n) < O(n log n) < O(n²)

Ответ

f1(n), f2(n), f3(n)

Почему константы не меняют порядок

Для маленьких n константы могут влиять на реальное время. Но Big-O сравнивает асимптотический рост: при достаточно больших входных данных n² неизбежно растёт быстрее, чем n log n, независимо от небольших множителей.

Полезный порядок сложностей

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!)

Как ответить на собеседовании

Сначала отбрасываю константы и слагаемые меньшего порядка, затем сравниваю доминирующие члены. В примере 3n + 100, n log n и n² порядок от более быстрой к более медленной функции будет: O(n), затем O(n log n), затем O(n²).