Что такое большое О или почему твои алгоритмы медленнее однорукой собаки

всем ку здарова. Ох, давно же меня не было. У меня есть для вас две новости: хорошая и плохая. Хорошая — я не умер, все хорошо. Плохая — я все еще жив. "Алексей, хватит тянуть" — скажите вы. "Потерпи, бездарь" — скажу я. Прежде всего хотел бы предупредить, что я не какой-то сверхгений алгоритмов и тоже могу ошибаться. Это мои мануальчики, которые можно читать либо для быстрой инфы, либо чтобы ха-ха словить. Спасибо.

Ну ладно, перейдем собсна к постику. Начнем с прелюдии))))(любимое)

Представьте, Вы — жоский крутой предприниматель. У вас аж целый бутик с женской обувью на рынке. Почесав свою репу, вы решаете, что надо в этой жизни дальше как-то двигаться и расширяться. А что делает каждый очень крутой бизнесмен? Конечно же открывает свой сайт по подбору обуви в своем бутике. Вы пересчитываете свои последние деньги и идете на фриланс, где находите сеньора Василия, который еще будучи в подгузнике интернет придумал(по его словам). Вы доверяете свой шедевро-сайт Василию и и платите ему последний лям баксов, который лежал на сберкнижке. Через n-ное количество времени вы принимаете работу и вот вроде бы все хорошо. Однако, после того, как вы разрекламили свой сайт, вы заметили, что когда на сайт заходит больше, чем 3.5 человека, то поиск на сайте отлетает моментом. Поиск грузится и ищет товары целую вечность. А все почему? Потому что Василий — не шарит за сложность алгоритмов и сделал все тяп-ляп. Вася сделал поиск, который каждый раз просматривает все товары и сравнивает их с запросом пользователя. А вы прикиньте, если на сайте будет 1.5 млн ботинков. Запрос пользователя будет сравниваться с каждым ботинком, что конечно же очень долго. Эх, Василий, Василий... Надо было бинарный поиск писать блин((

Но как Василию понять какой алгоритм лучше всего подойдет для решения той или иной задачи? Вот для этого умные дяди и тети придумали понятие Big O.

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

Что там с самой сложностью. Ну, по классике, есть несколько основных видов:

• O(1) — Константная сложность
  Это когда ваш алгоритм работает одинаково быстро, сколько бы данных вы ему ни скормили. Пример: вызов элемента из массива.

def a_sot_a(massiv):
    print(massiv[0]) # в массиве может быть хоть 100000000000 элементов, 
                     # он сразу их выведет

• O(n) — Линейная сложность
  Чем больше данных, тем дольше работает. Пример: поиск элемента в неотсортированном массиве.

def find_element(arr, target):
    for element in arr:  # Проходим по каждому элементу массива.
        if element == target:
            return True
    return False                                                          

• O(n²) — Квадратичная сложность
  Это когда ваш код начинает тормозить так, что кажется, будто вы ждете пока батя из толчка выйдет. Пример: пузырьковая сортировка.

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]  

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

def binary_search(arr, target):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2  # Делим массив пополам.
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1  # Ищем в правой половине.
        else:
            high = mid - 1  # Ищем в левой половине.
    return -1  # Элемент не найден.

• O(2^n) — Экспоненциальная сложность
  Это когда ваш код работает так медленно, что вы успеваете выпить чай, съесть бутерброд и посмотреть сериал, пока он думает. Пример: рекурсивное вычисление чисел Фибоначчи.

def fibonacci(n):
    if n <= 1:  # Базовый случай.
        return n
    return fibonacci(n-1) + fibonacci(n-2)  # Рекурсивный вызов.

Там еще есть несколько видов сложностей, но мне чет впадлу было для них код писать, изучим вот эти. Картиночку добавлю вам зумерам мелким вы ж без них не можете блин((

def get_last_element(arr):
    return arr[-1]  # Получаем последний элемент массива.

def find_max(arr):
    max_val = arr[0]
    for num in arr:
        if num > max_val:
            max_val = num
    return max_val

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]

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

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)  # merge — O(n)

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

Заключение: Так что же делать бедному Василию?

Ну что, друзья, подведем итоги.

Василий, конечно, молодец — сайт-то он сделал. Но вот с алгоритмами у него, мягко говоря, "не очень". Если бы он знал про Big O, то сразу бы понял, что перебирать 1.5 млн ботинков линейно — это как искать иголку в стоге сена, да еще и в темноте.

Выводы просты:

1. Big O — это не просто буквы, а важная штука, которая спасет ваш код от тормозов.
2. O(n²) — это боль, O(log n) — уже лучше, а O(1) — мечта.
3. Если ваш код работает на малых данных, но впадает в кому на больших — значит, вы где-то накосячили со сложностью.

Так что, дорогой читатель, теперь ты вооружен знанием. Можешь идти и поправить Василия (или даже самому не стать Василием). А если вдруг забудешь, что такое O(n log n) — просто представь, что это как сортировка носков в шкафу: быстро и эффективно.

P.S. Если твой код работает дольше, чем готовка пельменей без воды — пора переписывать. 🚀

(На этом всё. Спасибо, что дочитал. И да, Вася, если ты это читаешь — сорян, но учи матчасть.)