Урок 5: Оценка сложности алгоритмов (Big O)

Привет, ребята! Сегодня мы поговорим о важной теме в программировании — оценке сложности алгоритмов. Вы когда-нибудь задумывались, почему одни алгоритмы работают быстрее, чем другие? Или как выбрать наиболее эффективный способ решения задачи? Все это связано с оценкой сложности алгоритмов, и мы разберем, как это делать с помощью Big O-нотации

Почему принято рассказывать про сложности алгоритма и ее важность

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

Пример

Представьте, что вы ищете номер телефона в телефонной книге. Если вы будете просматривать каждый номер по очереди, это займет много времени. Но если вы будете использовать метод бинарного поиска в отсортированной книге, вы сможете найти номер гораздо быстрее. Это и есть разница в сложности алгоритмов

Обозначение сложности алгоритмов с помощью Big O-нотации

Big O-нотация — это способ описания сложности алгоритма в терминах роста времени выполнения или потребления памяти по мере увеличения размера входных данных. Основные классы сложности:

• O(1) — константная сложность. Время выполнения не зависит от размера входных данных.
• O(log n) — логарифмическая сложность. Время выполнения растет медленно по сравнению с увеличением входных данных
• O(n) — линейная сложность. Время выполнения пропорционально размеру входных данных.
• O(n log n) — линейно-логарифмическая сложность. Часто встречается в эффективных алгоритмах сортировки
• O(n²) — квадратичная сложность. Время выполнения пропорционально квадрату размера входных данных

Пример

Давайте рассмотрим два простых алгоритма для поиска элемента в массиве:

Линейный поиск (O(n)):

   def linear_search(arr, target):
       for i in range(len(arr)):
           if arr[i] == target:
               return i
       return -1

В этом алгоритме мы проходим по всем элементам массива, поэтому сложность — O(n).

Бинарный поиск (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

Здесь мы делим массив пополам на каждом шаге, что делает сложность O(log n).

Примеры вычисления сложности для различных алгоритмических конструкций

Теперь давайте разберем несколько примеров вычисления сложности для разных конструкций

Пример 1: Цикл

def sum_array(arr):
    total = 0
    for num in arr:
        total += num
    return total

Сложность этого алгоритма — O(n), так как мы проходим по каждому элементу массива

Пример 2: Вложенные циклы

def print_pairs(arr):
    for i in range(len(arr)):
        for j in range(len(arr)):
            print(arr[i], arr[j])

Здесь у нас два вложенных цикла, поэтому сложность — O(n²).

Пример 3: Рекурсия

def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n - 1)

Сложность этого алгоритма — O(n), так как мы вызываем функцию n раз

Сегодня мы рассмотрели, что такое сложность алгоритмов, как ее оценивать с помощью Big O-нотации и разобрали примеры различных алгоритмов. Понимание сложности алгоритмов поможет вам писать более эффективный код и выбирать оптимальные решения для задач.

Если у вас есть вопросы или вы хотите разобрать конкретные примеры, не стесняйтесь задавать их! Давайте обсудим, как мы можем применить эти знания на практике

Четвертый урок Псевдокод и блок-схемы

Практический урок Составление алгоритмов для решения простых задач