Какое основное вычислительное свойство у алгоритма?

# Основные вычислительные свойства алгоритма

Когда говорят об основном вычислительном свойстве алгоритма, обычно имеют в виду его сложность — количество операций, необходимых для решения задачи в зависимости от размера входных данных. Это критически важно для оценки производительности и масштабируемости.

Временная сложность (Time Complexity)

Основное вычислительное свойство — это временная сложность O(n), которая показывает, как время выполнения растёт с увеличением входных данных:

# O(1) — константная сложность
def get_first_element(arr):
    return arr[0]  # Одна операция, независимо от размера

# O(n) — линейная сложность
def find_max(arr):
    max_val = arr[0]
    for element in arr:  # Проходим n элементов
        max_val = max(max_val, element)
    return max_val

# O(n²) — квадратичная сложность
def bubble_sort(arr):
    for i in range(len(arr)):
        for j in range(len(arr) - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]

# O(log n) — логарифмическая сложность
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

Порядок роста сложности

От быстрой к медленной:

Пространственная сложность (Space Complexity)

Второе важное свойство — сколько дополнительной памяти требует алгоритм:

# O(1) — константная память
def sum_array(arr):
    total = 0  # Одна переменная
    for x in arr:
        total += x
    return total

# O(n) — линейная память
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    # Создаём новые массивы размером n
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

# O(log n) — логарифмическая (рекурсия)
def quick_sort(arr):
    # Глубина рекурсии ~ log n
    pass

Нотация Big O

Оценивает худший случай (worst case):

# Линейный поиск: O(n)
def search(arr, target):
    for item in arr:
        if item == target:
            return True
    return False  # Худший случай: элемента нет

Другие нотации:

• Ω (Omega) — лучший случай
• Θ (Theta) — средний случай

Правила расчёта

1. Отбрасываем константы: O(2n) = O(n)
2. Отбрасываем младшие члены: O(n² + n) = O(n²)
3. Умножаем при вложенных циклах: два вложенных цикла = O(n²)

# O(n) — одна константа отбрасывается
for i in range(1000):
    pass

# O(n) — доминирует линейная часть
for i in range(n):  # O(n)
    pass
for i in range(n):  # O(n)
    pass
# Результат: O(n + n) = O(n)

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

Практические выводы

• n < 10^6: приемлемо O(n log n) и O(n)
• n < 10^4: может работать O(n²)
• n > 10^8: нужно O(log n) или O(1)
• Для n = 20: даже O(2^n) может быть приемлемо

Основное вычислительное свойство — это фундамент для выбора алгоритма. Плохо выбранный алгоритм с худшей сложностью может быть в 1000+ раз медленнее на больших данных, чем оптимальный.