krahets
5.5 KiB
Что такое алгоритм
Определение алгоритма
Алгоритм -- это набор инструкций или шагов, предназначенных для решения конкретной задачи за ограниченное время, обладающий следующими свойствами:
- задача четко определена, включает ясные определения входных и выходных данных;
- обладает осуществимостью, может быть выполнен за ограниченное количество шагов, времени и памяти;
- каждый шаг имеет определенное значение, при одинаковых входных данных и условиях выполнения результат всегда будет одинаковым.
Определение структуры данных
Структура данных -- это способ организации и хранения данных, включающий содержимое данных, их взаимосвязи и методы операций с ними. Структура данных преследует следующие цели:
- минимизацию занимаемого пространства для экономии памяти компьютера;
- максимально быструю обработку данных, включая доступ, добавление, удаление и обновление данных;
- обеспечение простого представления данных и логической информации для эффективного выполнения алгоритмов.
Проектирование структуры данных -- это процесс, полный компромиссов. Если вы хотите улучшить один аспект, часто приходится идти на уступки в другом. Приведем два примера.
- Связный список, по сравнению с массивом, более удобен для добавления и удаления данных, но имеет проблемы со скоростью доступа к данным.
- Граф, по сравнению со связным списком, предоставляет более богатую логическую информацию, но требует большего объема памяти.
Взаимосвязь структур данных и алгоритмов
Структуры данных и алгоритмы тесно взаимосвязаны, что проявляется в следующих трех аспектах (см. рис. 1.4):
- структуры данных являются основой алгоритмов. Они обеспечивают структурированное хранение данных и методы их обработки;
- алгоритмы оживляют структуры данных. Сами по себе структуры данных лишь хранят информацию, но в сочетании с алгоритмами они позволяют решать конкретные задачи;
- алгоритмы можно реализовать на основе различных структур данных, однако эффективность их выполнения может значительно различаться. Поэтому выбор подходящей структуры данных является ключевым фактором.
Структуры данных и алгоритмы подобны конструктору, как показано на рис. 1.5. Комплект конструктора, помимо множества деталей, содержит также подробную инструкцию по сборке. Следуя этой инструкции шаг за шагом, можно собрать красивую модель.
Подробное описание аналогии с конструктором представлено в табл. 1.1.
Таблица 1.1. Сравнение структур данных и алгоритмов с конструктором
| Структуры данных и алгоритмы | Конструктор |
|---|---|
| Входные данные | Несобранные детали конструктора |
| Структура данных | Организация деталей конструктора, включая форму, размер, способы соединения и т. д. |
| Алгоритм | Последовательность действий по сборке деталей в целевую модель |
| Выходные данные | Собранная модель конструктора |
Стоит отметить, что структуры данных и алгоритмы не зависят от языка программирования. Именно поэтому данная книга предлагает их реализации на различных языках.