Алгоритм представляет собой пошаговую процедуру, которая определяет набор инструкций, которые должны быть выполнены в определенном порядке, чтобы получить желаемый результат. Алгоритмы, как правило, создаются независимо от базовых языков, то есть алгоритм может быть реализован на нескольких языках программирования.
С точки зрения структуры данных, ниже приведены некоторые важные категории алгоритмов —
-
Поиск — алгоритм поиска элемента в структуре данных.
-
Сортировка — алгоритм сортировки элементов в определенном порядке.
-
Вставить — Алгоритм вставки элемента в структуру данных.
-
Обновить — алгоритм обновления существующего элемента в структуре данных.
-
Удалить — алгоритм удаления существующего элемента из структуры данных.
Поиск — алгоритм поиска элемента в структуре данных.
Сортировка — алгоритм сортировки элементов в определенном порядке.
Вставить — Алгоритм вставки элемента в структуру данных.
Обновить — алгоритм обновления существующего элемента в структуре данных.
Удалить — алгоритм удаления существующего элемента из структуры данных.
Характеристики алгоритма
Не все процедуры можно назвать алгоритмом. Алгоритм должен иметь следующие характеристики —
-
Однозначный — алгоритм должен быть понятным и однозначным. Каждый из его этапов (или фаз) и их входы / выходы должны быть четкими и должны приводить только к одному значению.
-
Входные данные — алгоритм должен иметь 0 или более четко определенных входных данных.
-
Выходные данные — алгоритм должен иметь 1 или более четко определенных выходных данных и должен соответствовать желаемым выходным данным.
-
Конечность — Алгоритмы должны завершаться после конечного числа шагов.
-
Осуществимость — должно быть осуществимо с доступными ресурсами.
-
Независимо — алгоритм должен иметь пошаговые инструкции, которые не должны зависеть от программного кода.
Однозначный — алгоритм должен быть понятным и однозначным. Каждый из его этапов (или фаз) и их входы / выходы должны быть четкими и должны приводить только к одному значению.
Входные данные — алгоритм должен иметь 0 или более четко определенных входных данных.
Выходные данные — алгоритм должен иметь 1 или более четко определенных выходных данных и должен соответствовать желаемым выходным данным.
Конечность — Алгоритмы должны завершаться после конечного числа шагов.
Осуществимость — должно быть осуществимо с доступными ресурсами.
Независимо — алгоритм должен иметь пошаговые инструкции, которые не должны зависеть от программного кода.
Как написать алгоритм?
Нет четко определенных стандартов для написания алгоритмов. Скорее, это проблема и ресурсозависимый. Алгоритмы никогда не пишутся для поддержки определенного программного кода.
Поскольку мы знаем, что все языки программирования имеют общие базовые конструкции кода, такие как циклы (do, for, while), управление потоком (if-else) и т. Д. Эти общие конструкции могут использоваться для написания алгоритма.
Мы пишем алгоритмы пошагово, но это не всегда так. Написание алгоритма — это процесс, который выполняется после того, как проблемная область четко определена. То есть мы должны знать проблемную область, для которой мы разрабатываем решение.
пример
Давайте попробуем научиться писать алгоритмы на примере.
Проблема — Разработайте алгоритм для добавления двух чисел и отображения результата.
Step 1 − START Step 2 − declare three integers a , b & c Step 3 − define values of a & b Step 4 − add values of a & b Step 5 − store output of step 4 to c Step 6 − print c Step 7 − STOP
Алгоритмы говорят программистам, как кодировать программу. Альтернативно, алгоритм может быть записан как —
Step 1 − START ADD Step 2 − get values of a & b Step 3 − c ← a + b Step 4 − display c Step 5 − STOP
При разработке и анализе алгоритмов обычно для описания алгоритма используется второй метод. Это позволяет аналитику легко анализировать алгоритм, игнорируя все нежелательные определения. Он может наблюдать, какие операции используются и как протекает процесс.
Написание номера шагов , необязательно.
Мы разрабатываем алгоритм, чтобы получить решение данной проблемы. Проблема может быть решена несколькими способами.
Следовательно, многие алгоритмы решения могут быть получены для данной проблемы. Следующим шагом является анализ этих предложенных алгоритмов решения и реализация наиболее подходящего решения.
Алгоритм анализа
Эффективность алгоритма может быть проанализирована на двух разных этапах, до реализации и после реализации. Они следующие —
-
Априорный анализ — это теоретический анализ алгоритма. Эффективность алгоритма измеряется в предположении, что все другие факторы, например скорость процессора, являются постоянными и не влияют на реализацию.
-
Апостериорный анализ — это эмпирический анализ алгоритма. Выбранный алгоритм реализован с использованием языка программирования. Затем выполняется на целевом компьютере. В этом анализе собраны фактические статистические данные, такие как время выполнения и требуемое пространство.
Априорный анализ — это теоретический анализ алгоритма. Эффективность алгоритма измеряется в предположении, что все другие факторы, например скорость процессора, являются постоянными и не влияют на реализацию.
Апостериорный анализ — это эмпирический анализ алгоритма. Выбранный алгоритм реализован с использованием языка программирования. Затем выполняется на целевом компьютере. В этом анализе собраны фактические статистические данные, такие как время выполнения и требуемое пространство.
Мы узнаем об априорном алгоритме анализа. Анализ алгоритма имеет дело с выполнением или временем выполнения различных задействованных операций. Время выполнения операции может быть определено как количество компьютерных инструкций, выполненных за операцию.
Сложность алгоритма
Предположим, что X является алгоритмом, а n является размером входных данных, время и пространство, используемое алгоритмом X, являются двумя основными факторами, которые определяют эффективность X.
-
Фактор времени — Время измеряется путем подсчета количества ключевых операций, таких как сравнения, в алгоритме сортировки.
-
Коэффициент пространства — пространство измеряется путем подсчета максимального объема памяти, требуемого алгоритмом.
Фактор времени — Время измеряется путем подсчета количества ключевых операций, таких как сравнения, в алгоритме сортировки.
Коэффициент пространства — пространство измеряется путем подсчета максимального объема памяти, требуемого алгоритмом.
Сложность алгоритма f (n) дает время выполнения и / или объем памяти, требуемый алгоритмом, в терминах n в качестве размера входных данных.
Космическая сложность
Пространственная сложность алгоритма представляет собой объем памяти, необходимый алгоритму в его жизненном цикле. Пространство, требуемое алгоритмом, равно сумме следующих двух компонентов:
-
Фиксированная часть, представляющая собой пространство, необходимое для хранения определенных данных и переменных, которые не зависят от размера проблемы. Например, используемые простые переменные и константы, размер программы и т. Д.
-
Переменная часть — это пространство, необходимое для переменных, размер которых зависит от размера задачи. Например, динамическое выделение памяти, пространство стека рекурсии и т. Д.
Фиксированная часть, представляющая собой пространство, необходимое для хранения определенных данных и переменных, которые не зависят от размера проблемы. Например, используемые простые переменные и константы, размер программы и т. Д.
Переменная часть — это пространство, необходимое для переменных, размер которых зависит от размера задачи. Например, динамическое выделение памяти, пространство стека рекурсии и т. Д.
Пространственная сложность S (P) любого алгоритма P равна S (P) = C + SP (I), где C — фиксированная часть, а S (I) — переменная часть алгоритма, которая зависит от характеристики экземпляра I. простой пример, который пытается объяснить концепцию —
Algorithm: SUM(A, B) Step 1 - START Step 2 - C ← A + B + 10 Step 3 - Stop
Здесь у нас есть три переменные A, B и C и одна константа. Следовательно, S (P) = 1 + 3. Теперь пространство зависит от типов данных заданных переменных и типов констант, и оно будет соответственно умножено.
Сложность времени
Временная сложность алгоритма представляет собой количество времени, которое требуется алгоритму для выполнения до завершения. Требования ко времени могут быть определены как числовая функция T (n), где T (n) может быть измерено как количество шагов, при условии, что каждый шаг потребляет постоянное время.
Например, сложение двух n-битных целых чисел занимает n шагов. Следовательно, общее время вычислений равно T (n) = c ∗ n, где c — время, необходимое для сложения двух битов. Здесь мы видим, что T (n) растет линейно с увеличением размера ввода.