Что такое вычислительные алгоритмы и что означает нотация Big O

Вычислительные алгоритмы — это последовательность шагов для решения задачи, преобразования входных данных в выходные. Они должны быть корректными (давать правильный результат) и эффективными (использовать минимум ресурсов).

Big O — это асимптотическая нотация, описывающая верхнюю границу времени выполнения или использования памяти алгоритма в худшем случае. Она показывает, как растёт сложность при увеличении размера входных данных (n).

Примеры сложностей:

• O(1) – константная (доступ к элементу списка по индексу).
• O(n) – линейная (поиск в неотсортированном списке).
• O(n²) – квадратичная (пузырьковая сортировка).

# O(1) – доступ по индексу
value = my_list[0]  

# O(n) – линейный поиск
for item in my_list:  
    if item == target:  
        break  

# O(n²) – вложенные циклы  
for i in range(n):  
    for j in range(n):  
        print(i, j)  

Big O игнорирует константы и меньшие члены, фокусируясь на доминирующем факторе роста.