Откуда берется понятие временной сложности O(n) и почему она предпочтительнее O(n²)?

O(n) означает, что время выполнения алгоритма растет линейно с увеличением размера входных данных (n). Это происходит, когда алгоритм обрабатывает каждый элемент входных данных один раз или постоянное количество раз.

O(n²) означает, что время выполнения алгоритма растет квадратично с увеличением размера входных данных. Это типично для алгоритмов, где выполняются вложенные итерации по данным (например, два вложенных цикла, каждый из которых проходит по n элементам).

O(n) предпочтительнее O(n²) потому, что при увеличении размера входных данных (n) время выполнения алгоритма с временной сложностью O(n¹) растет значительно медленнее, чем у алгоритма с O(n²). Для больших n разница во времени выполнения становится очень существенной.

Пример: Если n = 1000: O(n) - время выполнения пропорционально 1000 O(n²) - время выполнения пропорционально 1000² = 1 000 000

python

python