Структуры данных: основы алгоритмов

Предыдущие статьи: “Руководство по структурам данных и алгоритмам: введение и настройка среды”

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

С точки зрения структур данных, важны следующие категории алгоритмов:

• Алгоритм поиска элемента в структуре данных.
• Алгоритм сортировки элементов в определенном порядке.
• Алгоритм вставки элемента в структуру данных.
• Алгоритм изменения имеющегося в структуре данных элемента.
• Алгоритм удаления элемента из структуры данных.

Характеристики алгоритма

Не все процедуры можно назвать алгоритмом. Алгоритм должен обладать следующими характеристиками:

• Однозначность. Алгоритм должен быть четким и однозначным. Каждый из его шагов, а также данные в вводе/выводе должны быть четкими и приводить только к одному значению.
• Входные данные. В алгоритме должны быть четко определенные входные данные, но входные данные могут и отсутствовать.
• Выходные данные. Алгоритм должен иметь четко определенные выходные данные и соответствовать желаемому результату.
• Конечность. Алгоритмы должны завершаться после конечного числа шагов.
• Осуществимость. Должен быть осуществим при имеющихся ресурсах.
• Независимость. Алгоритм должен иметь пошаговые инструкции, независимые от любого программного кода.

Как написать алгоритм?

Это, скорее, зависит от задачи и ресурсов. Четко определенных стандартов написания алгоритмов не существует. Алгоритмы никогда не пишут для поддержки того или иного программного кода.

Как известно, у всех языков программирования общие базовые конструкции кода, например циклы (do, for, while), управление потоком (if-else) и т. д. Эти общие конструкции могут быть использованы для написания алгоритма.

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

Пример

Попробуем научиться писать алгоритмы на примере.

Задача: разработать алгоритм сложения двух чисел и отображения результата:

Шаг 1 − НАЧАЛО ADD
Шаг 2 − объявляем три целых числа a, b и c
Шаг 3 − определяем значения a и b
Шаг 4 − добавляем значения a и b
Шаг 5 − сохраняем результат шага 4 в c
Шаг 6 − печатаем c
Шаг 7 − КОНЕЦ ADD

Алгоритмы сообщают программистам, как писать код программы. Алгоритм может быть написан и в таком виде:

Шаг 1 − НАЧАЛО ADD
Шаг 2 − получаем значения a и b
Шаг 3 − c ← a + b
Шаг 4 − отображение c
Шаг 5 − КОНЕЦ ADD

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

Писать номера шагов необязательно.

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

Поэтому для задачи могут быть разработаны алгоритмы с множеством решений. Следующий этап  —  анализ этих предложенных алгоритмов и реализация наиболее подходящего решения.

Анализ алгоритмов

Эффективность алгоритма можно проанализировать на двух разных этапах  —  до и после реализации. Вот эти этапы:

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

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

Сложность алгоритма

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

• Фактор времени. Время измеряется путем подсчета количества ключевых операций, например сравнений в алгоритме сортировки.
• Фактор пространства. Пространство измеряется путем подсчета максимального объема памяти, требующегося алгоритму.

Сложностью алгоритма f(n) определяется время выполнения и/или дисковое пространство, требующиеся алгоритму, где n  —  это размер входных данных.

Пространственная сложность

Пространственная сложность алгоритма представляет собой объем памяти, требующийся алгоритму в течение его жизненного цикла. Этот объем состоит из двух частей:

• Фиксированная часть, то есть пространство, необходимое для хранения определенных данных и переменных, не зависящих от размера задачи. Например, используемые простые переменные и константы, размер программы и т. д.
• Изменяемая часть, то есть пространство, необходимое переменным, зависящим от размера задачи. Например, динамическое выделение памяти, пространство стека рекурсии и т. д.

Пространственная сложность S(P) любого алгоритма P определяется как S(P) = C + SP(I), где C  —  это фиксированная , а SP(I)  —  это изменяемая часть алгоритма, зависящая от характеристики экземпляра I. Вот простой пример, объясняющий эту концепцию:

Алгоритм: SUM(A, B)
Шаг 1 -  НАЧАЛО
Шаг 2 -  C ← A + B + 10
Шаг 3 -  Конец

Здесь есть три переменные A, B, и C и одна константа. Поэтому пространственная сложность S(P) = 1 + 3. Пространство зависит от типов данных заданных переменных и типов констант и будет в соответствии с этим увеличиваться.

Временная сложность

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

Например, сложение двух n-битных целых чисел проходит в n шагов. Значит, общее вычислительное время составит T(n) = c ∗ n, где c  —  это время, необходимое для сложения двух битов. Здесь имеет место линейный рост T(n) по мере увеличения размера входных данных.

Читайте также:

• Как алгоритм «случайный лес» вычисляет продавцов-мошенников на онлайн-рынке
• 6 техник, которые помогут вам учиться лучше
• Почему люди подсаживаются на TikTok? Алгоритм ИИ, который вас подловил

Читайте нас в Telegram, VK и Яндекс.Дзен