Анализ алгоритмов (заметки)

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

Пусть даны два алгоритма f(n) и g(n).Если можно заключить первую функцию в границы второй , умноженную на одну константу( верхнее значение) и на другую для нижнего, то обе эти функции имеют одинаковый порядок роста.
ПРимер :РАсположить функции в порядке возрастания степени роста.

Конечные суммы . Формулы суммирования.
Фрормулы Арифметической и геометрической прогрессии.

Реккурентное соотношение.
-----------------------------------------------------------
Алгоритмы поиска.
1) ПОследовательный поиск.
Зависит от цели поиска и числа элементов.
For i:=1 to n do
Begin
IF then do
end;
Наилучший случай: СЛожность равна 1.
Наихудший случай: сложность равна N.

Анализ среднего случая.
-----------------------------------------------------------

2) ПОиск в упорядоченном списке( двоичный поиск).
Осуществляется путём последовательного разбиения отрезка значений пополам , отбрасывании неподходящего отрезка и рассмотрении подходящего( до тех пор пока поиск не завершиться).

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