Алгоритм и его свойства

Определение Алгоритма

Алгоритм - последовательность действий для исполнителя, записанная на формальном языке и приводящая к заданной цели за конечное время.

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

Основные свойства алгоритмов

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

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

Сложность алгоритма — это необходимый для его исполнения объём ресурсов. Чем алгоритм сложнее, тем больше машинных ресурсов он потребляет.

Временная сложность((O)-нотация): Описывает, как изменяется время выполнения алгоритма с увеличением размера входных данных.

Пространственная сложность: Аналогична временной сложности, но относится к использованию памяти.

Виды сложности алгоритмов

• Комбинаторная - минимальное число элементов для реализации алгоритма в виде вычислительных устройств.
• Относительная - длина описания алгоритма на формальном языке
• Вычислительная - количество элементарных операций для неких входных данных

O(1), O(n), O(n^2), O(n^3), O(2^n), O(n!)