Как понять, что алгоритм работает за линейное время относительно размера входных данных?

Алгоритм работает за линейное время (O(n)), если время его выполнения пропорционально размеру входных данных. Это значит, что при увеличении объёма данных в два раза время работы примерно удваивается.

Чтобы понять, что алгоритм линейный, можно:

• Проанализировать код и убедиться, что в нём есть один цикл, проходящий по всем элементам входа без вложенных циклов.
• Провести эксперимент: измерить время выполнения для разных размеров входных данных и проверить, что график времени примерно линейно растёт.

Пример линейного алгоритма на Python:

def sum_list(numbers):
    total = 0
    for num in numbers:
        total += num
    return total

Здесь время работы зависит от количества элементов в списке — это классический пример O(n).