Что такое BigO notation?

1️⃣ Как кратко ответить

Big O notation — это математическая нотация, используемая для описания производительности алгоритма в худшем случае. Она показывает, как время выполнения или использование памяти алгоритма увеличивается с ростом размера входных данных. Основные классы сложности: O(1), O(log n), O(n), O(n log n), O(n^2).

2️⃣ Подробное объяснение темы

Big O notation — это инструмент, который помогает оценить эффективность алгоритмов. Он используется для описания того, как изменяется время выполнения или использование памяти алгоритма в зависимости от размера входных данных. Это важно для понимания, насколько хорошо алгоритм будет работать с большими объемами данных.

Как работает Big O notation

Big O notation описывает асимптотическое поведение алгоритма, то есть его поведение при стремлении размера входных данных к бесконечности. Она игнорирует константы и менее значимые члены, фокусируясь на наиболее значимых факторах, влияющих на производительность.

Основные классы сложности

1. O(1) — Константная сложность
   Время выполнения не зависит от размера входных данных. Пример: доступ к элементу массива по индексу.

2. O(log n) — Логарифмическая сложность
   Время выполнения увеличивается логарифмически с увеличением размера входных данных. Пример: бинарный поиск.

3. O(n) — Линейная сложность
   Время выполнения увеличивается линейно с увеличением размера входных данных. Пример: простой перебор элементов массива.

4. O(n log n) — Линейно-логарифмическая сложность
   Время выполнения увеличивается линейно-логарифмически. Пример: эффективные алгоритмы сортировки, такие как быстрая сортировка и сортировка слиянием.

5. O(n^2) — Квадратичная сложность
   Время выполнения увеличивается квадратично с увеличением размера входных данных. Пример: сортировка пузырьком, вставками или выбором.

Пример кода

Рассмотрим пример алгоритма с разной сложностью:

# O(1) - Константная сложность
def get_first_element(arr):
    # Возвращает первый элемент массива
    return arr[0]
​
# O(n) - Линейная сложность
def find_element(arr, target):
    # Перебирает все элементы массива
    for element in arr:
        # Если элемент равен искомому, возвращает True
        if element == target:
            return True
    # Если элемент не найден, возвращает False
    return False
​
# O(n^2) - Квадратичная сложность
def bubble_sort(arr):
    n = len(arr)
    # Проходит по всем элементам массива
    for i in range(n):
        # Для каждого элемента проходит по оставшимся
        for j in range(0, n-i-1):
            # Если текущий элемент больше следующего, меняет их местами
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    # Возвращает отсортированный массив
    return arr

• get_first_element: Время выполнения не зависит от размера массива, так как доступ к элементу по индексу выполняется за постоянное время.
• find_element: В худшем случае необходимо проверить каждый элемент массива, что делает сложность линейной.
• bubble_sort: Для каждого элемента массива необходимо пройтись по всем оставшимся элементам, что приводит к квадратичной сложности.