Урок 1: Введение в алгоритмы и сложность $O(n)$

Добро пожаловать на первый урок по Алгоритмам! Если курс Python научил нас как писать код, то курс алгоритмов научит нас делать это эффективно.

Что такое алгоритм?
Алгоритм — это четкая инструкция для решения задачи. Приготовление чая, сборка LEGO по инструкции или поиск слова в словаре — всё это алгоритмы.

В программировании нас волнуют две вещи:

Время (как быстро работает программа).

Память (сколько места она занимает).

1. Как измерить скорость? (Big O Notation)
Мы не можем мерить скорость в секундах, потому что у одного ученика мощный компьютер, а у другого — старый ноутбук. Поэтому программисты используют Нотацию "О" большое.

Она показывает, как количество операций растет вместе с ростом данных.

2. Линейная сложность: $O(n)$Это самый простой вид сложности.
Представь, что тебе нужно найти нужную карту в колоде из $n$ карт, перебирая их по одной.Если карт 10 — нужно 10 действий.Если карт 1 000 000 — нужно 1 000 000 действий.Время растет прямо пропорционально количеству данных.

Практическая задача: «Линейный поиск»Давай напишем алгоритм, который ищет «сокровище» в списке.
Это классический пример сложности $O(n)$.Задача: Найти индекс числа в списке. Если числа нет — сообщить об этом.

def find_treasure(box, gold):
    steps = 0  # Считаем количество шагов
    for i in range(len(box)):
        steps += 1
        if box[i] == gold:
            print(f"Нашел за {steps} шагов!")
            return i
    print(f"Сокровища нет, проверено {steps} коробок.")
    return -1

# Проверка:
items = [10, 25, 43, 11, 98, 70]
find_treasure(items, 98)