Algorithms #1 | Big O: Hate math? Here you go

Что такое Алгоритмы #1 в названии?

- Это серия статей по алгоритмам и возможности получать вам оффер от Яндекса по 10 раз на день!!!)

Что такое Big O и почему это важно

Big O (или “О большое”) — это самая базовая база. Казалось бы, можно же просто засечь время выполнение программы, но вот досада... К сожалению на одном компьютере код будет выполняться 1 секунду, а уже на другом больше 20 секунд просто из-за того что у другого железо хуже. Ну и короче что бы уметь сравнивать, без этих сложностей, придумали Big O!

Если умными словами:
Big O - показывает зависимость числа выполняемых операций от размера входных данных.


Теперь нырнем немного глубже...
Какие виды сложности алгоритмов Big O вообще есть:

О(1) - Константная сложность
Время выполнения не зависит от размера входных данных. Доступ к элементу массива по его индексу. Процессору нужно просто вычислить адрес в памяти, что занимает фиксированное количество тактов.

Пример: Есть приложение которое выводит данные первого элемента массива, при любой ситуации время выполнения данной программы будет всегда константным (не изменяемым). Из-за этого и получается O(1) - 1 идет как константа.

Пример кода:

def print_first_item(items):
print(items[0])

Python

def print_first_item(items):

    print(items[0])

О(N) - Линейная сложность
Сложность растет прямо пропорционально количеству входных данных.

Пример: Представь, что тебе нужно найти одну конкретную папку в ряду, но папки никак не подписаны. Тебе приходится подходить к первой, открывать, смотреть. Не то. Подходишь ко второй... и так до самого конца. Если на полке 10 папок - ты потратишь минуту. Если привезли еще один стеллаж и папок стало 100 - ты потратишь 10 минут.

Пример кода:

def find_item(items, target):
for item in items:
if item == target:
return True # Проверяем каждый элемент по очереди
return False

Python

def find_item(items, target):

    for item in items:

        if item == target:

            return True # Проверяем каждый элемент по очереди

    return False

O(log N) - Логарифмическое время или "Умный поиск"
Это когда на каждом шаге ты отбрасываешь половину данных.

Пример: Самый популярный пример это бинарный поиск. Сначала смотришь середину, потом либо левую половину, либо правую - и так далее...

Пример кода:

def binary_search(sorted_list, target):
low = 0
high = len(sorted_list) - 1

while low <= high:
mid = (low + high) // 2
if sorted_list[mid] == target:
return mid # Нашли!
elif sorted_list[mid] < target:
low = mid + 1 # Отбрасываем левую половину
else:
high = mid - 1 # Отбрасываем правую половину
return None

Python

def binary_search(sorted_list, target):

    low = 0

    high = len(sorted_list) - 1

 

    while low <= high:

        mid = (low + high) // 2

        if sorted_list[mid] == target:

            return mid # Нашли!

        elif sorted_list[mid] < target:

            low = mid + 1 # Отбрасываем левую половину

        else:

            high = mid - 1 # Отбрасываем правую половину

    return None

О(N * log N)- почти линейно, но с «умной» обработкой или "Профессиональная сортировка"
Представь, что у тебя есть N элементов, и тебе нужно их как-то обработать или отсортировать. Линейный проход по всем элементам - это O(N). Но что если внутри каждого шага ты ещё выполняешь логарифмическое действие, типа деления данных пополам, поиска или объединения?

Пример: Merge sort (сортировка слиянием) или Quick sort (быстрая сортировка). Ты берёшь весь список (N элементов) и делишь его пополам, потом снова делишь половинки и так до самых маленьких кусочков. Потом соединяешь всё обратно, аккуратно сортируя. В итоге проходишь по каждому элементу несколько раз, но не бесконечно - количество делений растёт очень медленно (log N).

Пример кода:

def merge_sort(items):
if len(items) <= 1:
return items

# 1. Делим список пополам (это дает log n)
mid = len(items) // 2
left_half = merge_sort(items[:mid])
right_half = merge_sort(items[mid:])

# 2. Соединяем их обратно, просматривая элементы (это дает n)
return merge(left_half, right_half)


def merge(left, right):
result = []

while left and right:
if left[0] <= right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))

result.extend(left)
result.extend(right)
return result

Python

def merge_sort(items):

    if len(items) <= 1:

        return items



    # 1. Делим список пополам (это дает log n)

    mid = len(items) // 2

    left_half = merge_sort(items[:mid])

    right_half = merge_sort(items[mid:])



    # 2. Соединяем их обратно, просматривая элементы (это дает n)

    return merge(left_half, right_half)





def merge(left, right):

    result = []

   

    while left and right:

        if left[0] <= right[0]:

            result.append(left.pop(0))

        else:

            result.append(right.pop(0))

   

    result.extend(left)

    result.extend(right)

    return result

О(N*N) или O(N^2) - квадратичное время
Это когда у тебя есть два вложенных действия, зависящих от одного и того же набора данных. Если говорить не много проще - ты берёшь каждый элемент и для него проходишься по всем остальным.

Пример: Допустим, у тебя есть список из N чисел, и ты хочешь сравнить каждое число с каждым. Сначала берешь первый и сравниваешь его со всеми, потом второй со всеми и так далее... В итоге получается такая операция:
N * N = N^2
Если брать какой то пример из жизни, например на вечеринке тебе нужно познакомить 5 друзей друг с другом, это получается 25 рукопожатий (не много). Если друзей 10 это уже 100 рукопожатий и оно может очень быстро рости.

Пример кода:

def introduce_friends(friends):
count = 0 # Счётчик рукопожатий

# Первый (внешний) цикл: берем по очереди каждого друга
for friend_a in friends:

# Второй (вложенный) цикл: для выбранного друга проходим по ВСЕМ остальным
for friend_b in friends:
# Печатаем процесс знакомства
print(f"{friend_a} пожимает руку {friend_b}")
count += 1

print(f"Итого сделано рукопожатий: {count}")

# Наш список друзей (N = 5)
my_friends = ["Алексей", "Мария", "Иван", "Диана", "Кирилл"]

introduce_friends(my_friends)

Python

def introduce_friends(friends):

    count = 0  # Счётчик рукопожатий

 

    # Первый (внешний) цикл: берем по очереди каждого друга

    for friend_a in friends:

     

        # Второй (вложенный) цикл: для выбранного друга проходим по ВСЕМ остальным

        for friend_b in friends:

            # Печатаем процесс знакомства

            print(f"{friend_a} пожимает руку {friend_b}")

            count += 1

         

    print(f"Итого сделано рукопожатий: {count}")



# Наш список друзей (N = 5)

my_friends = ["Алексей", "Мария", "Иван", "Диана", "Кирилл"]



introduce_friends(my_friends)

О(2^N) - экспоненциальное время
Это когда при добавлении каждого нового элемента количество операций удваивается.

Пример: Перебор всех вариантов. Допустим, у тебя есть N элементов, и для каждого есть 2 варианта: "взять" и "не взять". Тогда общее количество комбинаций получается 2^N. Это часто встречается в задачах с комбинациями, решениях рекурсией и в задачах типа «подмножества».
Самый близкий пример из жизни это выбор одежды. Если ты выбрал 1 вещь - у тебя есть 2 варианта: "взять" или "не взять". Если выбрал 2, то уже 4 комбинации. Если 10 - то это уже 1024 комбинации.

Пример кода:

def get_all_outfits(items):
outfits = [[]] # Начинаем с пустого набора (вариант "ничего не взяли")

for item in items:
new_outfits = []
for outfit in outfits:
# Для каждого уже существующего набора создаем новый,
# добавляя в него текущую вещь (вариант "взяли")
new_outfits.append(outfit + [item])

# Объединяем старые наборы (где вещи нет) с новыми (где вещь есть)
outfits.extend(new_outfits)

# На каждом шаге размер списка outfits удваивается!
print(f"Добавили вещь '{item}': теперь у нас {len(outfits)} комбинаций")

return outfits

my_clothes = ["Футболка", "Джинсы", "Кепка"]
all_combinations = get_all_outfits(my_clothes)

Python

def get_all_outfits(items):

    outfits = [[]] # Начинаем с пустого набора (вариант "ничего не взяли")

 

    for item in items:

        new_outfits = []

        for outfit in outfits:

            # Для каждого уже существующего набора создаем новый,

            # добавляя в него текущую вещь (вариант "взяли")

            new_outfits.append(outfit + [item])

     

        # Объединяем старые наборы (где вещи нет) с новыми (где вещь есть)

        outfits.extend(new_outfits)

     

        # На каждом шаге размер списка outfits удваивается!

        print(f"Добавили вещь '{item}': теперь у нас {len(outfits)} комбинаций")

 

    return outfits



my_clothes = ["Футболка", "Джинсы", "Кепка"]

all_combinations = get_all_outfits(my_clothes)

О(N!) - факториальное время
Это когда алгоритм перебирает все возможные порядки элементов. Не просто «взять или не взять» (как в 2^N), а именно переставить всё всеми возможными способами.

Пример: Представь, что у тебя есть список дел, и ты хочешь попробовать все возможные порядки, чтобы найти лучший. С 3-мя делами - это 6 вариантов. С 10 делами уже получается миллионы вариантов.
Если все еще не понятно, вот пример из моего опыта в разработке:
У меня была поставлена задача разработать алгоритм, который будет выдавать самый быстрый маршрут для перевозки груза, который проходит через нужные точки. Самое простое решение этой задачи это перебрать все возможные маршруты и после выбрать лучший - это и есть O(N!) !!!

Пример кода:

import itertools

def find_all_routes(cities):
# Метод permutations создает ВСЕ возможные последовательности
# Это и есть реализация N!
routes = list(itertools.permutations(cities))

count = 0
for route in routes:
# Представь, что здесь мы считаем длину каждой дороги
# print(f"Проверяем маршрут: {' -> '.join(route)}")
count += 1

return count

# Список городов
locations = ["Москва", "Питер", "Казань", "Сочи", "Екатеринбург"]

total_routes = find_all_routes(locations)
print(f"Для {len(locations)} городов существует {total_routes} вариантов маршрута.")

Python

import itertools



def find_all_routes(cities):

    # Метод permutations создает ВСЕ возможные последовательности

    # Это и есть реализация N!

    routes = list(itertools.permutations(cities))

 

    count = 0

    for route in routes:

        # Представь, что здесь мы считаем длину каждой дороги

        # print(f"Проверяем маршрут: {' -> '.join(route)}")

        count += 1

     

    return count



# Список городов

locations = ["Москва", "Питер", "Казань", "Сочи", "Екатеринбург"]



total_routes = find_all_routes(locations)

print(f"Для {len(locations)} городов существует {total_routes} вариантов маршрута.")

Примечание

Для обозначения входных данных, используют переменную N, но по желаю можно использовать на самом деле любую букву =)

Если вам было интересно и понятно, ну или не понятно, хотел бы что бы вы оставили свой комментарий. Хочется сделать максимально доступным и простым такую сложную тему как Алгоритмы...

Новая статья уже скоро! =0

​