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

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

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

Search - Алгоритм поиска элемента в структуре данных.
Sort - Алгоритм сортировки предметов в определенном порядке.
Insert - Алгоритм вставки элемента в структуру данных.
Update - Алгоритм обновления существующего элемента в структуре данных.
Delete - Алгоритм удаления существующего элемента из структуры данных.

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

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

Unambiguous- Алгоритм должен быть четким и однозначным. Каждый из его шагов (или фаз) и их входы / выходы должны быть ясными и иметь только одно значение.
Input - Алгоритм должен иметь 0 или более четко определенных входов.
Output - Алгоритм должен иметь 1 или несколько четко определенных выходов и должен соответствовать желаемому выходу.
Finiteness - Алгоритмы должны завершаться после конечного числа шагов.
Feasibility - Должно быть осуществимо при имеющихся ресурсах.
Independent - Алгоритм должен иметь пошаговые инструкции, которые не должны зависеть от программного кода.

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

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

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

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

пример

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

Problem - Разработайте алгоритм сложения двух чисел и отображения результата.

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

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

Письмо step numbers, не является обязательным.

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

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

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

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

A Priori Analysis- Это теоретический анализ алгоритма. Эффективность алгоритма измеряется исходя из предположения, что все другие факторы, например скорость процессора, постоянны и не влияют на реализацию.
A Posterior Analysis- Это эмпирический анализ алгоритма. Выбранный алгоритм реализован на языке программирования. Затем это выполняется на целевом компьютере. В этом анализе собирается фактическая статистика, такая как время работы и необходимое пространство.

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

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

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

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

Сложность алгоритма 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) линейно растет с увеличением размера ввода.