Алгоритмы и структуры данных на языке Kotlin

Введение в алгоритмизацию: оценка сложности (Big O) и базовые конструкции Kotlin

Добро пожаловать на курс «Алгоритмы и структуры данных на языке Kotlin». Мы начинаем наше путешествие с фундаментальных понятий, без которых невозможно стать профессиональным разработчиком. Сегодня мы разберем, что такое алгоритм, почему важно уметь оценивать его эффективность и как язык Kotlin помогает писать чистый и безопасный код.

Что такое алгоритм?

В самом широком смысле алгоритм — это четкая последовательность действий, приводящая к решению поставленной задачи за конечное число шагов. Это не просто код, это рецепт.

Представьте, что вы готовите яичницу. Ваш алгоритм может выглядеть так:

В программировании алгоритмы работают с данными. Сортировка списка контактов в телефоне, построение маршрута в навигаторе или рекомендация видео на YouTube — все это результат работы алгоритмов.

Свойства хорошего алгоритма

Чтобы инструкция считалась алгоритмом, она должна обладать следующими свойствами: * Дискретность: процесс разбит на отдельные простые шаги. * Определенность (детерминированность): каждый шаг понятен однозначно, нет места для двоякого толкования. При одних и тех же входных данных результат всегда одинаков. * Конечность: алгоритм должен завершаться за разумное время. * Массовость: алгоритм должен работать для целого класса задач, а не только для одного конкретного случая (например, сортировать любой массив чисел, а не только массив [1, 5, 3]).

Оценка сложности алгоритмов: Big O Notation

Написать работающий код — это только полдела. Важно написать эффективный код. Но как измерить эффективность? Секундомером? Это плохой способ, так как время выполнения зависит от мощности компьютера, загруженности системы и даже температуры процессора.

Нам нужен универсальный способ оценки, который не зависит от «железа». Для этого используется нотация Big O («О» большое).

Big O описывает, как меняется время выполнения алгоритма (или потребляемая память) при увеличении объема входных данных.

!График сравнения временной сложности алгоритмов: от константной до экспоненциальной

Рассмотрим основные классы сложности, с которыми вы будете сталкиваться чаще всего.

— Константная сложность

Время выполнения не зависит от количества данных. Неважно, 10 элементов в массиве или 10 миллионов — операция займет одно и то же время.

Пример из жизни: вы берете книгу с полки, зная её точное местоположение.

— Линейная сложность

Время выполнения растет прямо пропорционально количеству данных. Если данных стало в 2 раза больше, алгоритм будет работать в 2 раза дольше.

Формально это можно записать так:

где — время выполнения, — некоторая константа (время на одну операцию), а — количество элементов.

Пример из жизни: чтение книги страница за страницей. Чем толще книга, тем дольше вы читаете.

— Квадратичная сложность

Время выполнения растет пропорционально квадрату количества элементов. Это часто встречается в алгоритмах с вложенными циклами. Если данных стало в 2 раза больше, время увеличится в 4 раза ().

Математически это выражается как:

где — время выполнения, — константа, — количество элементов, а показывает квадратичную зависимость.

— Логарифмическая сложность

Очень эффективная сложность. Время растет очень медленно при увеличении данных. Характерна для алгоритмов, которые на каждом шаге отсекают половину данных (например, бинарный поиск).

Формула:

где — время, — константа, — двоичный логарифм от количества элементов .

> «Преждевременная оптимизация — корень всех зол». > — Дональд Кнут [The Art of Computer Programming]

Это означает, что не стоит сразу гнаться за , если ваш код становится нечитаемым, а данных мало. Но понимать сложность необходимо, чтобы не написать алгоритм, который «повесит» сервер при нагрузке.

Базовые конструкции Kotlin для алгоритмов

Kotlin — современный, статически типизированный язык, который идеально подходит для реализации алгоритмов благодаря своей лаконичности и безопасности. Рассмотрим конструкции, которые мы будем использовать на протяжении всего курса.

Переменные: val и var

В алгоритмах важно понимать, меняется ли состояние переменной.

* val (value) — неизменяемая ссылка (аналог final в Java или const в C++). Используйте её по умолчанию. * var (variable) — изменяемая переменная.

Циклы и диапазоны

Большинство алгоритмов требуют итерации (перебора). В Kotlin цикл for работает с диапазонами и коллекциями очень элегантно.

Функции

Алгоритмы оформляются в виде функций. В Kotlin функции объявляются ключевым словом fun.

Примеры алгоритмов на Kotlin с разбором сложности

Давайте реализуем несколько простых алгоритмов и оценим их сложность, используя полученные знания.

1. Линейный поиск (Linear Search)

Задача: Найти, есть ли определенное число в массиве.

Алгоритм: Идем по массиву слева направо и сравниваем каждый элемент с искомым.

Анализ сложности: В худшем случае (элемента нет или он в самом конце) нам придется проверить все элементов. Следовательно, сложность — .

2. Проверка на дубликаты (Naive approach)

Задача: Проверить, есть ли в массиве повторяющиеся числа.

Алгоритм: Берем первый элемент и сравниваем его со всеми остальными. Потом берем второй и сравниваем с оставшимися, и так далее.

Анализ сложности: Здесь мы видим вложенные циклы. Внешний цикл выполняется раз. Внутренний цикл выполняется примерно раз для каждой итерации внешнего.

Общее количество операций пропорционально:

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

Сложность — . Это медленный алгоритм. Если , то количество операций будет около .

3. Доступ к элементу массива

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

Анализ сложности: Компьютер знает адрес начала массива в памяти и может мгновенно вычислить адрес любого элемента по индексу. Неважно, какой длины массив. Сложность — .

Итоги

Сегодня мы заложили фундамент для всего курса:

В следующей статье мы подробно разберем массивы и списки, узнаем разницу между Array и ArrayList в Kotlin, и научимся писать эффективные алгоритмы для работы с ними.

Алгоритмы сортировки и поиска: от пузырьковой сортировки до бинарного поиска

В предыдущей статье мы познакомились с понятием алгоритмической сложности и нотацией Big O. Мы выяснили, что эффективность кода измеряется не секундами, а тем, как растет количество операций при увеличении входных данных.

Сегодня мы перейдем от теории к практике и разберем два класса задач, с которыми программисты сталкиваются ежедневно: сортировка и поиск. Мы начнем с простых, но неэффективных решений, и постепенно придем к алгоритмам, которые используются в реальных высоконагруженных системах.

Почему сортировка так важна?

Представьте, что вы ищете слово в словаре. Если слова расположены в алфавитном порядке, вы найдете нужное за несколько секунд. Если же слова перемешаны случайным образом, вам придется прочитать весь словарь от корки до корки.

> «Порядок освобождает мысль». > — Раймон Пуанкаре

Сортировка данных — это фундамент для эффективного поиска. Без нее многие быстрые алгоритмы просто не могут работать.

Пузырьковая сортировка (Bubble Sort)

Это один из самых простых для понимания алгоритмов сортировки, хотя и один из самых медленных. Его редко используют в реальных проектах (кроме учебных целей или очень маленьких массивов), но он отлично демонстрирует принцип алгоритмического мышления.

Принцип работы

Алгоритм многократно проходит по списку, сравнивает соседние элементы и меняет их местами, если они стоят в неправильном порядке (например, левый больше правого). В результате более «тяжелые» элементы (большие числа) «оседают» в конце списка, как пузырьки воздуха поднимаются на поверхность воды.

!Визуализация процесса сравнения и перестановки соседних элементов в пузырьковой сортировке

Реализация на Kotlin

Давайте напишем функцию сортировки для массива целых чисел.

Анализ сложности

В этом алгоритме мы видим два вложенных цикла.

Количество сравнений можно выразить формулой арифметической прогрессии:

где — сумма операций сравнения, а — количество элементов в массиве.

В нотации Big O мы отбрасываем константы и младшие степени, поэтому сложность пузырьковой сортировки составляет .

Это означает, что если увеличить массив в 10 раз, время сортировки увеличится примерно в 100 раз. Для больших данных этот алгоритм непригоден.

Быстрая сортировка в Kotlin

В реальной разработке вам не нужно писать сортировку вручную. Стандартная библиотека Kotlin использует оптимизированные алгоритмы (обычно это вариации QuickSort или TimSort), которые работают намного быстрее — в среднем за .

Поиск данных: Линейный vs Бинарный

Теперь, когда у нас есть отсортированные данные, мы можем поговорить о поиске.

Линейный поиск (Linear Search)

Мы уже рассматривали его в прошлой статье. Это простой перебор всех элементов подряд.

* Сложность: . * Плюс: Работает на несортированных данных. * Минус: Медленный на больших объемах.

Бинарный поиск (Binary Search)

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

#### Принцип работы

Представьте, что я загадал число от 1 до 100. Вы должны угадать его, а я буду говорить «больше» или «меньше».

С каждым шагом вы отсекаете ровно половину вариантов.

!Схематичное изображение процесса деления массива пополам при бинарном поиске

#### Реализация на Kotlin

#### Анализ сложности

На каждом шаге мы делим количество элементов на 2. Вопрос в том, сколько раз нужно разделить на 2, чтобы получить 1?

Это определение логарифма. Количество шагов выражается формулой:

где — количество шагов алгоритма, — размер массива, а — двоичный логарифм от .

Сложность бинарного поиска — .

#### Сравнение эффективности

Давайте сравним линейный и бинарный поиск для массива из 1 миллиарда элементов ().

| Алгоритм | Сложность | Максимум операций (худший случай) | | :--- | :--- | :--- | | Линейный поиск | | 1 000 000 000 (1 миллиард) | | Бинарный поиск | | |

Разница колоссальная: 30 операций против миллиарда! Именно поэтому поддержание данных в отсортированном виде так важно для баз данных и поисковых систем.

Использование бинарного поиска в Kotlin

Как и с сортировкой, в Kotlin бинарный поиск уже реализован в стандартной библиотеке.

Важно: Метод binarySearch корректно работает только если коллекция уже отсортирована. Если применить его к неотсортированному списку, результат будет непредсказуемым.

Заключение

Сегодня мы разобрали:

В следующей статье мы углубимся в структуры данных и узнаем, как работают связные списки (Linked Lists), и чем они отличаются от обычных массивов с точки зрения управления памятью.

Линейные структуры данных: реализация стеков, очередей и связных списков

В предыдущих статьях мы изучили массивы и алгоритмы сортировки. Массивы — это прекрасный инструмент: они обеспечивают мгновенный доступ к данным по индексу. Однако у них есть существенный недостаток: фиксированный размер и сложность вставки элементов. Если вы хотите добавить элемент в середину массива, вам придется сдвинуть все последующие элементы, что затратно для процессора.

Сегодня мы познакомимся с линейными динамическими структурами данных, которые решают эти проблемы. Мы разберем, как работают связные списки, стеки и очереди, реализуем их на Kotlin и выясним, когда их стоит использовать.

Связные списки (Linked Lists)

Связный список — это коллекция элементов, где каждый элемент (узел) хранит не только свои данные, но и ссылку на следующий элемент. В отличие от массива, элементы связного списка не обязаны располагаться в памяти последовательно. Они могут быть разбросаны по всей оперативной памяти, но «знают» друг о друге благодаря ссылкам.

!Структура односвязного списка: каждый узел указывает на следующий.

Анатомия узла

Базовый строительный блок списка — это Узел (Node). На языке Kotlin это можно представить как простой класс:

Здесь value — это полезная нагрузка (данные), а next — ссылка на следующий узел. Если next равен null, значит, мы достигли конца списка.

Реализация односвязного списка

Давайте создадим простую реализацию списка, который умеет добавлять элементы в начало и выводить содержимое.

``kotlin class LinkedList<T> { private var head: Node<T>? = null

// Добавление элемента в начало: O(1) fun push(value: T) { val newNode = Node(value = value, next = head) head = newNode }

// Проверка на пустоту fun isEmpty(): Boolean = head == null

// Печать списка fun printList() { var current = head while (current != null) { print("O(n)nO(1)O(1)O(n){stack.peek()}") // Третья книга

// Операция Pop (забрать) while (!stack.isEmpty()) { println("Забираем: {queue.peek()}") // Клиент 1

// Обслуживаем очередь (dequeue) while (!queue.isEmpty()) { println("Обслужен: T(n)O(1)nO(1)O(n)O(1)O(n)O(n)O(1)O(1)O(n)O(1)O(1)O(1)O(n)$).* \* При наличии ссылки на хвост списка (tail).*

Заключение

Мы разобрали три фундаментальные структуры данных:

В языке Kotlin класс ArrayDeque` является универсальным солдатом, который может выступать и в роли стека, и в роли очереди.

В следующей статье мы перейдем к более сложным, нелинейным структурам данных и изучим Хеш-таблицы (Hash Tables), которые позволяют искать данные мгновенно.

Деревья и графы: алгоритмы обхода в ширину (BFS) и глубину (DFS)

Мы прошли долгий путь от простых переменных до линейных структур данных — массивов, связных списков, стеков и очередей. Эти структуры отлично подходят для хранения данных, которые можно выстроить в одну линию, подобно очереди в магазине или списку дел.

Но как быть, если данные имеют иерархическую структуру? Например, файловая система вашего компьютера (папки внутри папок) или структура HTML-страницы. А если данные представляют собой сложную сеть, как карта метро или связи между друзьями в социальной сети? Линейные списки здесь бессильны.

Сегодня мы переходим в мир нелинейных структур данных: деревьев и графов. Мы узнаем, как они устроены, и разберем два фундаментальных алгоритма для навигации по ним: BFS и DFS.

Что такое граф?

Начнем с самого общего понятия. Граф — это абстрактная математическая модель, представляющая собой множество объектов и связей между ними.

Граф состоит из двух множеств:

где (Vertices) — множество вершин (узлов), а (Edges) — множество ребер (связей) между ними.

!Абстрактное представление графа с вершинами и ребрами

Примеры графов в реальной жизни:

Способы представления графа в коде

Существует два основных способа хранения графа:

В Kotlin граф можно представить как Map, где ключ — это вершина, а значение — список смежных вершин.

Что такое дерево?

Дерево — это частный случай графа. Это связный граф, в котором нет циклов. Это означает, что из одной точки в другую существует только один путь.

У дерева есть особые свойства: * Корень (Root): Верхний узел иерархии (в программировании деревья растут корнями вверх). * Родитель и Ребенок: Если узел A ссылается на узел B, то A — родитель, B — ребенок. * Лист (Leaf): Узел, у которого нет детей.

!Иерархическая структура дерева: корень вверху, листья внизу

В Kotlin узел бинарного дерева (где у каждого родителя не более двух детей) выглядит так:

Алгоритмы обхода

Представьте, что вы потеряли ключи в огромном замке с множеством комнат (вершин) и коридоров (ребер). Вам нужно обойти замок, чтобы найти ключи. Как вы будете это делать? Хаотично бегать? Или использовать систему?

В программировании существует два системных подхода к обходу графов и деревьев.

1. Поиск в глубину (Depth-First Search — DFS)

Стратегия: «Иди вперед, пока можешь. Если зашел в тупик — вернись назад на развилку и иди по другому пути».

Этот алгоритм напоминает прохождение лабиринта по правилу «держаться правой руки». Мы погружаемся вглубь структуры настолько далеко, насколько это возможно, прежде чем вернуться.

Структура данных: Для реализации DFS используется Стек (Stack). Вспомните нашу прошлую лекцию: принцип LIFO (Last In, First Out). Чаще всего стек реализуется неявно через рекурсию (стек вызовов функций).

#### Реализация DFS на Kotlin (Рекурсия)

Как это работает: Мы заходим в A. Всех соседей A (B, C, D) ставим в очередь. Затем берем B, обрабатываем его, а его соседей ставим в конец очереди (после D). Таким образом, мы не приступим к «внукам» A, пока не обработаем всех «детей» A.

Оценка сложности (Big O)

Для обоих алгоритмов (BFS и DFS) временная сложность одинакова:

где — количество вершин (Vertices), а — количество ребер (Edges).

Почему так? В худшем случае нам нужно посетить каждую вершину () ровно один раз и проверить каждое ребро (), выходящее из нее, чтобы найти соседей.

Пространственная сложность (память): * DFS: , где — максимальная глубина (высота) дерева или длина пути в графе. В худшем случае (узкий длинный граф) это . * BFS: , где — максимальная ширина дерева (количество узлов на одном уровне). В худшем случае это тоже может быть близко к .

Когда и что использовать?

Выбор между BFS и DFS зависит от задачи.

Используйте BFS (Ширина), если:

Используйте DFS (Глубина), если:

Заключение

Деревья и графы окружают нас повсюду: от DOM-дерева в браузере до маршрутизации пакетов в интернете. Понимание того, как обходить эти структуры, отличает новичка от инженера.

Главное, что нужно запомнить: * DFS — это про смелость и глубину. Использует Стек (или рекурсию). * BFS — это про осторожность и планомерность. Использует Очередь.

В следующей статье мы рассмотрим Хеш-таблицы — структуру данных, которая позволяет искать элементы за , и узнаем, как работают HashMap и HashSet под капотом Kotlin.

Оптимизация решений: введение в динамическое программирование и жадные алгоритмы

В предыдущих статьях мы научились хранить данные в стеках, очередях и деревьях, а также обходить сложные структуры с помощью BFS и DFS. Но часто перед программистом стоит задача не просто найти путь или сохранить данные, а найти лучший способ решения задачи.

Как проложить маршрут в навигаторе, чтобы потратить меньше всего бензина? Как разменять купюру минимальным количеством монет? Как уложить вещи в рюкзак, чтобы их ценность была максимальной, а вес не превышал лимит?

Сегодня мы познакомимся с двумя мощными подходами к решению оптимизационных задач: жадными алгоритмами и динамическим программированием. Мы разберем их на примерах, напишем код на Kotlin и выясним, когда «жадность» полезна, а когда она ведет к ошибкам.

Жадные алгоритмы (Greedy Algorithms)

Жадный алгоритм — это подход, при котором на каждом шаге принимается решение, которое кажется наилучшим в данный момент. Алгоритм не заглядывает в будущее и не отменяет свои решения. Он надеется, что серия локально оптимальных выборов приведет к глобально оптимальному решению.

Пример: Задача о размене монет

Представьте, что вы работаете вендинговым автоматом. Вам нужно выдать сдачу в 67 рублей, используя монеты номиналом 1, 5, 10 и 50 рублей. Ваша цель — использовать минимальное количество монет.

Логика жадного алгоритма:

Давайте проследим за процессом:

Итог: 50, 10, 5, 1, 1. Всего 5 монет. Это действительно оптимальное решение.

!Визуализация работы жадного алгоритма при выборе монет для сдачи.

Реализация на Kotlin

Когда жадность не работает?

Жадные алгоритмы быстры и просты в реализации. Их сложность часто составляет из-за сортировки или даже . Но у них есть фатальный недостаток: они работают не для всех наборов данных.

Изменим условия. Пусть у нас есть монеты номиналом 1, 3 и 4 рубля. Нам нужно набрать 6 рублей.

Жадный подход:

Оптимальный подход:

Жадный алгоритм ошибся! Он погнался за сиюминутной выгодой (взял четверку) и упустил лучшую комбинацию. Именно для таких случаев нам нужно динамическое программирование.

Динамическое программирование (Dynamic Programming)

Динамическое программирование (DP) — это метод решения сложных задач путем разбиения их на более простые подзадачи. Главное отличие от простой рекурсии заключается в том, что мы запоминаем результаты подзадач и используем их повторно, вместо того чтобы вычислять заново.

У DP есть два ключевых свойства:

Пример 1: Числа Фибоначчи

Классический пример. Последовательность Фибоначчи задается формулой:

где — -е число Фибоначчи, — предыдущее число, а — предпредыдущее число.

#### Наивная рекурсия (Плохо)

Почему это плохо? Чтобы вычислить fib(5), мы вычисляем fib(4) и fib(3). Но внутри fib(4) мы снова вычисляем fib(3)! Мы делаем одну и ту же работу много раз. Сложность такого алгоритма — , что катастрофически медленно для больших .

!Дерево вызовов показывает, как одни и те же значения вычисляются многократно.

#### Мемоизация (Memoization) — Подход «сверху вниз»

Мы можем создать массив (или хеш-таблицу) и записывать туда уже вычисленные значения. Это называется мемоизация.

Теперь сложность алгоритма — , так как каждое число мы вычисляем ровно один раз.

#### Табуляция — Подход «снизу вверх»

Вместо рекурсии мы можем просто заполнить массив от начала до конца.

Пример 2: Исправление задачи о монетах

Вернемся к задаче, где жадный алгоритм провалился: монеты [1, 3, 4], сумма 6.

Мы будем использовать массив dp, где dp[i] будет хранить минимальное количество монет для суммы i.

Формула перехода:

где — искомое минимальное количество монет для суммы , — номинал -й монеты, а означает, что мы берем эту монету.

По сути, мы говорим: «Чтобы набрать сумму 6, мы можем взять монету 4 и добавить оптимальное решение для суммы 2, ИЛИ взять монету 3 и добавить решение для суммы 3... и выбрать минимум из этих вариантов».

#### Реализация DP на Kotlin

Давайте проследим заполнение массива dp для монет [1, 3, 4]:

* dp[0] = 0 * dp[1]: берем монету 1 -> dp[0] + 1 = 1. * dp[2]: берем монету 1 -> dp[1] + 1 = 2. * dp[3]: берем монету 1 -> dp[2] + 1 = 3. ИЛИ берем монету 3 -> dp[0] + 1 = 1. Минимум — 1. * ... * dp[6]: ... минимум будет получен из dp[3] + 1 (где dp[3] = 1). Итог 2.

!Процесс заполнения массива DP: решение строится на основе предыдущих вычислений.

Сравнение подходов

| Характеристика | Жадный алгоритм | Динамическое программирование | | :--- | :--- | :--- | | Принцип | Локально оптимальный выбор на каждом шаге | Полный перебор вариантов с запоминанием результатов | | Скорость | Очень быстро | Медленнее (часто полиномиальное время) | | Гарантия оптимума | Нет (зависит от задачи) | Да (если задача имеет оптимальную подструктуру) | | Сложность реализации | Низкая | Средняя / Высокая | | Примеры | Сжатие Хаффмана, Алгоритм Дейкстры | Рюкзак, Расстояние Левенштейна, Фибоначчи |

Заключение

Сегодня мы сделали важный шаг от простого написания кода к его оптимизации.

В реальной разработке на Kotlin вы будете сталкиваться с DP не каждый день, но понимание этого принципа научит вас видеть структуру задачи и избегать лишних вычислений. А вот жадные подходы встречаются повсеместно, особенно в системном программировании и работе с ресурсами.

В следующей статье мы рассмотрим Хеш-таблицы — структуру данных, которая обеспечивает мгновенный доступ к информации и часто используется в паре с динамическим программированием для мемоизации.