Под алгоритмом понимается всякое точное
предписание,
которое задаёт вычислительный процесс
(называемый в этом случае
алгоритмическим),
начинающийся с произвольного исходного
данного (из некоторой совокупности
возможных для данного алгоритма исходных
данных)
и направленный на получение полностью
определяемого этим исходным данным
результата.
Пример (алгоритм Евклида)
1. Ввести два числа – a и b.
2. Если a < b , поменять их местами.
3. Если b = 0 , то (Ответ: a ; Конец).
4. Положить r равным остатку от деления
a на b.
5. Заменить a на b.
6. Заменить b на r.
7. Перейти к п.3.
Сложность алгоритма
Временная сложность алгоритма — это
функция размера входных и выходных
данных, равная максимальному
количеству элементарных операций,
проделываемых алгоритмом для
решения экземпляра задачи указанного
размера.
Сложность алгоритма
Пространственная сложность алгоритма — это
функция размера входных и выходных
данных, равная максимальному объёму
памяти, затраченной алгоритмом для
решения экземпляра задачи указанного
размера.
Во многих задачах размер выхода не превосходит
размера входа или пропорционален ему — в
этом случае можно рассматривать
соответствующую сложность как функцию
размера только входных данных.
