Алгоритмы и структуры данных для начинающих: Ваш первый шаг к эффективному коду

Представь, что ты собираешь шкаф. У тебя есть инструкция и набор деталей. Можно закручивать шурупы отвёрткой, а можно молотком. Шкаф вроде бы соберётся в обоих случаях. Но во втором - криво, долго и с сорванными шурупами.

В программировании так же. Одну и ту же задачу можно решить по-разному. Быстро и чисто. Или медленно и вслепую.

Ты уже умеешь компилировать и запускать код на C++. Мы прошли это в статье «Первые шаги в C++: ставим среду, пишем и запускаем код». Твой код работает. Но ты чувствуешь: что-то не так. Может, он тормозит. Может, ты решаешь задачу «в лоб» и подозреваешь, что есть путь лучше. Это нормально. Значит, ты готов к следующему шагу.

Теперь мы научимся писать так, чтобы код не тормозил в Docker-контейнере и не создавал проблем в CI/CD из-за долгих тестов.

К концу этой статьи ты поймёшь, что такое Big O. Узнаешь массив и связный список в лицо. Напишешь свой первый алгоритм линейного поиска на C++. И научишься измерять его скорость. Это твой первый шаг к эффективному коду.

Мы работаем на C++. Python появится только в одном месте - в аккордеоне для сравнения синтаксиса. Учить его не нужно.

1. Что такое алгоритм и структура данных

Алгоритм

Простыми словами, алгоритм - это проверенный рецепт. Пошаговая инструкция для решения конкретной задачи.

Как рецепт борща. Нарезал, обжарил, залил, варил 40 минут. Переставил шаги местами - получил не борщ, а недоразумение. В программировании алгоритм работает так же. Это последовательность действий, которая получает входные данные и выдаёт результат.

Примеры алгоритмов окружают нас повсюду. Утренний сбор на работу - алгоритм. Рецепт блинов - алгоритм. Путь от дома до метро - тоже алгоритм. Ты пользуешься алгоритмами каждый день. Просто не называешь их так.

Структура данных

Простыми словами, структура данных - это способ организовать и хранить наши «ингредиенты». Чтобы повару было удобно с ними работать.

Муку - в банку. Специи - на полку. Овощи - в ящик. Каждому продукту - своё место. В программировании структура данных - это контейнер для хранения данных. С определёнными правилами доступа и операциями.

Алгоритм без правильной структуры данных - как повар без организованной кухни. Вроде готовит, но половину времени ищет ингредиенты. Одно без другого работает плохо.

2. Как измерить эффективность: Big O Notation

Ты в библиотеке. Тебе нужна книга. Можно передавать её по одной странице - это долго. А можно отдать всю книгу целиком - это быстро.

Big O - это не точное время в секундах. Это ответ на вопрос: «Как быстро растёт время выполнения, если данных становится больше?»

Big O измеряет не процессорное время и не такты. Он измеряет количество операций, которые совершает алгоритм, когда размер входных данных стремится к бесконечности. Это «верхняя планка». Худший сценарий.

Давай разберём три главные нотации. Без формул. На аналогиях.

O(1) - константное время. «Мгновенно»

Ты знаешь, что книга - на полке №15, третья слева. Подошёл и взял. Не важно, 100 книг в библиотеке или 100 000. Ты всё равно подходишь к нужной полке. Количество книг не влияет на время.

В коде это выглядит как доступ к элементу массива по индексу. arr[5]. Одна операция. Всегда.

O(n) - линейное время. «Пропорционально»

Ты ищешь книгу с дарственной надписью от бабушки. Но не помнишь, где она. Приходится просматривать каждую книгу на полке. Это долго. 10 книг - 10 проверок. 1000 книг - 1000 проверок. Видишь закономерность?

В 100 раз больше книг - в 100 раз дольше. Это линейный поиск. Простой перебор массива в цикле for.

O(n²) - квадратичное время. «Лавина»

Ты сравниваешь каждый подарок с каждым. Чтобы никому не подарить одинаковое. 5 подарков - 25 сравнений. 100 подарков - 10 000 сравнений. Лавина.

В коде это вложенный цикл for внутри for. Каждый новый элемент умножает работу, а не прибавляет.

График Big O Notation. Зелёная горизонтальная прямая - O(1). Жёлтая наклонная - O(n). Красная парабола - O(n²).

3. Инструмент №1 - Массив

Ряд пронумерованных почтовых ящиков в подъезде. Все ящики одного размера. Стоят ровно в ряд. Ты сразу знаешь номер нужного. Ящик №0, ящик №1, ящик №2. Подошёл - и ты там.

Массив устроен так же. Элементы одного типа - int, double, char. Расположены в памяти подряд, друг за другом. У каждого элемента есть индекс. Начинается с 0. Размер фиксирован - ты должен сразу знать, сколько ящиков понадобится.

Плюсы. Доступ по индексу за O(1). Хочешь пятый элемент - arr[5] - и ты там. Просто. Понятно даже новичку.

Минусы. Вставка и удаление в середину - дорого. Приходится сдвигать все элементы справа. Размер изменить нельзя для статического массива C++.

Реальный кейс. Хранение пикселей изображения. Фотография 1000×1000 пикселей - это массив из миллиона элементов. Чтобы осветлить картинку, программа проходит по каждому пикселю и меняет его значение. Доступ к пикселю по координатам - это доступ к массиву по индексу. O(1) для каждого пикселя.

#include <iostream>
using namespace std;

int main() {
    int arr[5] = {10, 20, 30, 40, 50};
    cout << arr[2] << endl; // 30 - доступ за O(1)
    return 0;
}

4. Инструмент №2 - Связный список

Квест. Охота за сокровищами. Ты находишь первую записку: «Иди к старому дубу». Под дубом - вторая записка: «Ищи под скамейкой у фонтана».

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

Связный список устроен так же. Он состоит из узлов. Каждый узел содержит данные и указатель на следующий узел. Узлы могут быть разбросаны по памяти. Они не лежат подряд. Последний узел указывает в «никуда».

Плюсы. Вставка и удаление в любое место - быстро. Достаточно переставить указатели. Не нужно двигать тонну данных. Размер не фиксирован. Можно добавлять узлы, пока есть память.

Минусы. Доступ по индексу - O(n). Чтобы добраться до пятого узла, надо пройти через первые четыре. Индекса list[5] нет. Занимает больше памяти: под каждый элемент хранится ещё и указатель на следующий.

Реальный кейс. История действий с отменой в текстовом редакторе. Каждое действие пользователя - это узел. Когда ты нажимаешь Ctrl+Z, редактор идёт по цепочке обратно и восстанавливает предыдущее состояние. Добавить новое действие - быстро, O(1). Надо только переставить указатели. А искать конкретное действие по номеру почти никогда не нужно. Мы ходим вперёд-назад.

Не будем изобретать велосипед. В C++ уже есть готовая реализация связного списка - std::list. Давай посмотрим, как с ним работать:

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> myList = {10, 20, 30};

    // Пройти по списку
    for (int item : myList) {
        cout << item << " ";
    }
    // Вывод: 10 20 30

    // Вставить элемент в середину - быстро
    auto it = myList.begin();
    advance(it, 1); // Перемещаемся ко второму элементу
    myList.insert(it, 15);
    // Теперь список: 10 15 20 30

    return 0;
}

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* next; // Указатель на следующий узел. Если следующего нет - nullptr
};

int main() {
    Node* head = new Node{10, nullptr};
    head->next = new Node{20, nullptr};
    head->next->next = new Node{30, nullptr};

    // Пройти по списку
    Node* current = head;
    while (current != nullptr) {
        cout << current->data << " ";
        current = current->next;
    }
    // Вывод: 10 20 30

    // Не забудь удалить память
    delete head->next->next;
    delete head->next;
    delete head;

    return 0;
}

5. Попробуй сам - линейный поиск на C++

Пришло время написать свой первый алгоритм. Это линейный поиск. Простой. Понятный. Но это твой первый шаг к эффективному коду.

Задача. Написать функцию, которая получает массив имён и искомое имя. Возвращает индекс первого вхождения или -1, если имя не найдено.

Конкретные данные:

• Массив: ["Анна", "Борис", "Вера", "Глеб", "Диана"]
• Ищем: "Вера"
• Ожидаемый результат: индекс 2

Почему линейный поиск? Это простейший алгоритм сложности O(n). Идеальный первый алгоритм для новичка. Ты уже писал циклы в статье «Первые шаги в C++: ставим среду, пишем и запускаем код». Теперь ты даёшь циклу имя и измеряешь его скорость.

Пошаговая инструкция:

1. Создай массив строк из 5 имён.
2. Напиши функцию linearSearch, которая принимает массив, его размер и строку для поиска.
3. В функции пройди циклом по массиву и сравнивай каждый элемент с искомым.
4. Если нашёл - верни индекс. Не нашёл - верни -1.
5. Выведи результат на экран.

#include <iostream>
#include <string>
using namespace std;

int linearSearch(string arr[], int size, string target) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) {
            return i; // Нашли - возвращаем индекс
        }
    }
    return -1; // Не нашли
}

int main() {
    string names[5] = {"Анна", "Борис", "Вера", "Глеб", "Диана"};
    string target = "Вера";

    int result = linearSearch(names, 5, target);

    if (result != -1) {
        cout << "Имя \"" << target << "\" найдено на позиции " << result << endl;
    } else {
        cout << "Имя \"" << target << "\" не найдено" << endl;
    }

    return 0;
}

Критерии успеха:

• Программа компилируется без ошибок: g++ -std=c++17 -o search search.cpp.
• Для «Вера» выводит Имя "Вера" найдено на позиции 2.
• Если поменять target на "Елена", выводит Имя "Елена" не найдено.
• Проверка крайнего случая: в статическом массиве C++ размер 0 невозможен. Для проверки крайнего случая используй массив из 1 элемента и ищи то, чего в нём нет - алгоритм должен корректно вернуть -1. Это важно. Мы говорили об этом в ошибке №6.
• Проверка отсутствующего элемента: это уже сделано через "Елена".

Мини-задание - почувствуй O(n) на практике

Увеличь массив до 10 имён. Проверь, сколько сравнений делает алгоритм для первого элемента и для последнего. Как это сделать - вот готовая подсказка:

int linearSearch(string arr[], int size, string target) {
    int counter = 0; // Счётчик сравнений
    for (int i = 0; i < size; i++) {
        counter++; // Увеличиваем при каждом сравнении
        if (arr[i] == target) {
            cout << "Сравнений: " << counter << endl;
            return i;
        }
    }
    cout << "Сравнений: " << counter << endl;
    return -1;
}

Проверь для «Анна» - первого элемента. Проверь для последнего элемента в массиве из 10 имён. Сравни цифры.

Это O(n) в действии. Чем дальше элемент, тем больше работы. В лучшем случае - 1 сравнение. В худшем - все 10. В среднем - 5. Прямая зависимость. Никакой магии.

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

names = ["Анна", "Борис", "Вера", "Глеб", "Диана"]
target = "Вера"

result = linear_search(names, target)
if result != -1:
    print(f'Имя "{target}" найдено на позиции {result}')
else:
    print(f'Имя "{target}" не найдено')

6. Типичные ошибки начинающих

7. Что дальше

В следующей статье «Тестирование кода: юнит-тесты на Python/Java/C#» ты напишешь свой первый юнит-тест. Ты проверишь алгоритм линейного поиска, который создал сегодня, и убедишься, что он работает именно так, как ты задумал. Без ручного перезапуска программы. Автоматически. Один запуск - и ты знаешь, что всё в порядке.

Эта статья открывает модуль «Фундаментальные знания» из дорожной карты «Путь начинающего разработчика: дорожная карта от нуля до первой работы». Алгоритмы и структуры данных - это 90% технических собеседований на позицию начинающего разработчика. Ты только что сделал первый шаг в сторону, которую многие новички обходят стороной. А потом удивляются, почему их не берут на работу. Теперь ты знаешь то, что выделяет думающего разработчика из толпы.

Полезные внешние ресурсы:

• Хочешь увидеть, как разные алгоритмы ведут себя на разных данных? Зайди на visualgo.net - это визуализатор алгоритмов и структур данных. Введи свои числа и смотри, как сортировка или поиск работают по шагам.
• Хочешь системно изучить алгоритмы дальше? Начни с бесплатного курса Algorithms, Part I от Принстонского университета (Кевин Уэйн, Роберт Седжвик). Он на английском, но с русскими субтитрами на YouTube. Это следующий уровень после нашей статьи.

8. Шпаргалка

Заключение

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

Ты написал свой первый алгоритм. Не выучил чужой. Не скопировал. Написал сам. Понимая, что такое O(n). Это огромный шаг.

В следующей статье ты научишься проверять свой код автоматически - юнит-тестами. Твой линейный поиск больше никогда не сломается незаметно. Ты будешь знать об этом сразу. Прямо во время написания кода. Алгоритмы без тестов - это полдела. Алгоритмы с тестами - это профессиональный уровень.

Открой свой редактор кода. Запусти линейный поиск. Поиграйся с массивом - добавь 10 имён, 20 имён. Почувствуй, как работает O(n) на практике. Проверь крайние случаи: массив с одним элементом, отсутствующий элемент. Это лучшее, что ты можешь сделать прямо сейчас для своего роста как разработчика.