Привет, с сегодняшнего дня мы начнем разбирать самые популярные алгоритмы, которые вам точно пригодятся 😀

И сегодня поговорим про алгоритм о-Большое 🧠

Что такое «О большое» и зачем это знать?

«О большое» (Big O notation) — это способ описания того, как быстро растет время выполнения (или потребление памяти) алгоритма при увеличении размера входных данных. 😀

Она отвечает на главный вопрос: «Что произойдет с производительностью, если данных станет в 10, 100 или миллион раз больше?»

Важно: «О большое» описывает асимптотическую сложность — поведение при стремлении размера данных к бесконечности. Мы отбрасываем константы и младшие члены.

Основные виды сложности (от лучшей к худшей)

Обозначение Название Пример
O(1) Константная Доступ к элементу массива по индексу
O(log n) Логарифмическая Бинарный поиск в отсортированном массиве
O(n) Линейная Простой поиск перебором
O(n log n) Линейно-логарифмическая Быстрая сортировка, сортировка слиянием
O(n²) Квадратичная Пузырьковая сортировка, два вложенных цикла
O(2ⁿ) Экспоненциальная Рекурсивный подсчет чисел Фибоначчи (наивно) 😀

Примеры алгоритмов на Python и Go

Возьмем три типичных случая: O(1), O(n), O(n²).

1. Константный алгоритм O(1)
Время не зависит от размера входных данных.

Python 📱

def get_first_element(arr):
    return arr[0]  # Одна операция, сколько бы элементов ни было

data = [10, 20, 30, 40, 1000]
print(get_first_element(data))  # 10

Go 😀

package main

import "fmt"

func getFirstElement(arr []int) int {
    return arr[0] // O(1)
}

func main() {
    data := []int{10, 20, 30, 40, 1000}
    fmt.Println(getFirstElement(data)) // 10
}

2. Линейный алгоритм O(n)
Время растет пропорционально размеру входных данных.

Задача: найти сумму всех элементов массива.

Python 📱

def sum_array(arr):
    total = 0
    for num in arr:   # Цикл выполняется n раз
        total += num
    return total

print(sum_array([1, 2, 3, 4, 5]))  # 15

Go 😀

func sumArray(arr []int) int {
    total := 0
    for _, num := range arr { // O(n)
        total += num
    }
    return total
}

3. Квадратичный алгоритм O(n²)
Время растет квадратично — опасно для больших данных.

Задача: найти все пары элементов, сумма которых четна.

Python 📱

def find_even_sum_pairs(arr):
    result = []
    n = len(arr)
    for i in range(n):
        for j in range(n):   # Вложенный цикл — O(n²)
            if (arr[i] + arr[j]) % 2 == 0:
                result.append((arr[i], arr[j]))
    return result

print(find_even_sum_pairs([1, 2, 3]))
# [(1, 1), (1, 3), (2, 2), (3, 1), (3, 3)]

Go 😀

func findEvenSumPairs(arr []int) [][2]int {
    var result [][2]int
    n := len(arr)
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ { // O(n²)
            if (arr[i]+arr[j])%2 == 0 {
                result = append(result, [2]int{arr[i], arr[j]})
            }
        }
    }
    return result
}

Как анализировать сложность?

1. Смотри на циклы — вложенные циклы часто дают умножение сложностей.
2. Рекурсия — может давать O(2ⁿ), если каждый вызов порождает два новых.
3. Отбрасывай константы — O(2n) → O(n).
4. Бери верхнюю границу — если в алгоритме есть O(n) + O(n²), то общая сложность O(n²).

Почему это важно?🤔

· Выбор структуры данных: поиск в массиве — O(n), в хеш-таблице — O(1).
· Масштабирование: алгоритм O(n²) при n = 1 000 000 может работать годами.
· Интервью: без понимания Big O не пройти техническое собеседование.

Короткое резюме💃

«О большое» — это язык, на котором разработчики говорят о производительности алгоритмов, не привязываясь к скорости процессора или языку программирования.

Научившись оценивать сложность, ты начнешь писать код, который не ломается при росте данных, а плавно замедляется предсказуемым образом.
Ставь - 👍, если зашел формат с стикерами

#ProIT