Этапы построения алгоритма.

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

А если В; В если С; и т.д

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

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

Пример: Составить алгоритм решения уравнения ах=7

Исходные данные: а -произвольное число

Выходные данные: х -корень уравнения

Математическая модель: х=7/а

п1 задать число а

п2 если а<>0, то х=7/а. Перейти к п4

п3 если а=0, то записать - нет решения. Перейти к п5

п4 записать ответ - значение х

п5 конец

Этапы построения алгоритма:

- Постановка задачи

- Построение модели

- Разработка алгоритма

- Проверка правильности алгоритма

- Анализ алгоритма и его сложности

- Проверка программы

- Составление документации

Оценка сложности алгоритмов

Существует несколько способов измерения сложности алгоритма.

Программисты обычно сосредотачивают внимание на скорости алгоритма, но не менее важны и другие показатели – требования к объёму памяти, свободному месте на диске. Использование быстрого алгоритма не приведёт к ожидаемым результатам, если для его работы понадобится больше памяти, чем есть у компьютера.

Память или время

Многие алгоритмы предлагают выбор между объёмом памяти и скоростью. Задачу можно решить быстро, использую большой объём памяти, или медленнее, занимая меньший объём.

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

Результат будет получен мгновенно, но это потребует огромного объёма памяти. Карта большого города может содержать десятки тысяч точек. Тогда, описанная выше таблица, должна содержать более 10 млрд. ячеек. Т.е. для того, чтобы повысить быстродействие алгоритма, необходимо использовать дополнительные 10 Гб памяти.

Из этой зависимости проистекает идея объёмно-временной сложности. При таком подходе алгоритм оценивается, как с точки зрении скорости выполнения, так и с точки зрения потреблённой памяти.

Мы будем уделять основное внимание временной сложности, но, тем не менее, обязательно будем оговаривать и объём потребляемой памяти.

Оценка порядка

При сравнении различных алгоритмов важно знать, как их сложность зависит от объёма входных данных. Допустим, при сортировке одним методом обработка тысячи чисел занимает 1 с., а обработка миллиона чисел – 10 с., при использовании другого алгоритма может потребоваться 2 с. и 5 с. соответственно. В таких условиях нельзя однозначно сказать, какой алгоритм лучше.

В общем случае сложность алгоритма можно оценить по порядку величины. Алгоритм имеет сложность O(f(n)), если при увеличении размерности входных данных N, время выполнения алгоритма возрастает с той же скоростью, что и функция f(N).

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

1. C – константа

2. log(log(N))

3. log(N)

4. N^C, 0<C<1

5. N

6. N*log(N)

7. N^C, C>1

8. C^N, C>1

9. N!