Самостоятельная работа №1 По предмету: Алгоритмы проектирования Статические и динамические меры сложности алгоритма

Критерии оценки алгоритма
Единственный критерий измерения веса(RVC) предполагает, что каждый шаг алгоритма выполняется в единицу времени, а ячейка памяти — в единицу размера (заведомо постоянная).
Логарифмическая шкала(LCV) учитывает размер операнда, обрабатываемого конкретной операцией, и значение, хранящееся в ячейке памяти.
Временная сложность LCVОн определяется значением l (O p ), где O p — значение операнда.
Сложность грузоподъемности LCVОн определяется значением λ (М), где М — размер ячейки памяти.
Общие характеристики оценки сложности
Теперь мы перечислим некоторые из наиболее часто используемых функций для вычисления сложности. Задания перечислены в порядке возрастания сложности. Чем выше функция в этом списке, тем быстрее будет работать алгоритм с этим предположением.
1. С постоянна
2. лог (лог(Н))
3. лог(Н)
4. Н^С,
8. С^Н, С>1
9. Н!
Если мы хотим оценить сложность алгоритма, уравнение сложности которого содержит несколько таких функций, уравнение можно свести к функции из таблицы. Например, O (log (N) + N!) = O (N!). Если алгоритм вызывается нечасто на небольшом количестве данных, сложность O(N^2) можно считать приемлемой, но если алгоритм работает в реальном времени, производительности O(N) не всегда будет достаточно. Как правило, алгоритмы сложности N*log(N) работают с хорошей скоростью. Алгоритмы сложности N^C можно использовать только при малых значениях S, порядок которых определяется функциями C^N и вычислительной сложностью алгоритмов N! очень большой, поэтому только небольшое количество таких алгоритмов
Анализ алгоритмов; лучшее, худшее и среднее время безотказной работы.
При рассмотрении различных алгоритмов решения одной задачи полезно проанализировать, сколько вычислительных ресурсов (времени работы, памяти) они требуют, и выбрать наиболее эффективный. Конечно, нам нужно договориться о том, какая модель расчета используется. В этом туториале в качестве модели по большей части мы используем простую процессорную машину с произвольным доступом (random-access machine, операции с оперативной памятью для параллельного выполнения не предусмотрены).
Сложность алгоритма — это величина, отражающая порядок величины требуемого ресурса (времени или дополнительной памяти) в зависимости от размера задачи. Таким образом, мы различаем временную T(n) и пространственную V(n) сложность алгоритма. При рассмотрении оценки сложности мы используем временную сложность. Аналогично оценивается пространственная сложность. Самый простой способ оценки - экспериментальный, то есть программирование алгоритма и выполнение полученной программы на нескольких задачах, оценка времени выполнения программ. Однако этот метод имеет ряд недостатков. Во-первых, экспериментальное программирование — потенциально дорогостоящий процесс. Во-вторых, следует помнить, что на время выполнения программ влияют следующие факторы:
1. Временная сложность алгоритма программы;
2. Качество скомпилированного кода исполняемой программы;
3. Машинные инструкции, используемые для выполнения программы.
Наличие второго и третьего факторов не позволяет использовать типовые единицы временной сложности алгоритма (секунды, миллисекунды и т.д.), так как при наличии разных программистов (которые программируют алгоритм) можно получить разные оценки по тому же алгоритму. собственный), разные компиляторы и разные компьютеры. Часто временная сложность алгоритма зависит от размера входных данных. Обычно говорят, что это порядок временной сложности алгоритма T (на основе входных данных размера n) n . На практике очень сложно определить точное значение T(n). Поэтому обратимся к асимптотическому соотношению
О- буквы.
Существует метод, теоретически вычисляющий время выполнения алгоритма, о котором речь пойдет позже.

Для расчета общего времени выполнения процедуры Insertion-Sort мы указываем ее стоимость (количество операций) и сколько раз эта строка выполняется рядом с каждой строкой. Для каждого j от 2 до n (где n = length[A] — размер массива) нам нужно посчитать, сколько раз выполняется строка 5, это число мы обозначаем через tj. Строки внутри цикла выполняются на один раз меньше, чем проверка, потому что последняя проверка выходит из цикла. Строковое значение c, повторенное t раз, вносит cm — общее количество операций (однако это выражение нельзя использовать для расчета объема используемой памяти). Если мы сложим вклады всех строк, мы получим

Время выполнения процесса зависит не только от n, но и от того, какой массив размера n подан на вход. Оптимальный случай для процедуры Insertion-Sort — когда массив уже отсортирован. Тогда период строки заканчивается через 5 после первой проверки (поскольку A [ i ] ≤ main для i = j - 1), поэтому все tj в сумме равно 1, и

Таким образом, в наиболее удобном случае время t(n), размер необходим для сортировки ряда n, линейной функции (линейной функции от n) по n, например, a и b для некоторых констант T(n ) = аЕсть форма n+b. Эта константа определяется выбранными значениями с 1,..., с 8. Если массив находится в обратном (убывающем) порядке, время выполнения процедуры максимально: A[j] должен сравнить каждый элемент со всеми элементами A[1], ..., A[j - 1]. Кроме того, tj = j . Потому что

мы понимаем, что худший сценарий — это время процедуры.

В этом случае T(n) является квадратом (квадратичной функцией), т.е. имеет вид T ( n ) = aп 2 + бн + с. Константы A, b и c определяются здесь значениями c 1,..., c 8.
Обычно говорят, что порядок временной сложности алгоритма равен T (n размер входных данных) n . На практике очень сложно определить точное значение T(n). Поэтому они ссылаются на асимптотические соотношения с помощью O-символики. Например, если количество действий (действий), необходимых для работы алгоритма, равно 16п 2 + 12нвойти n + 2представлен n + 3, то алгоритм означает, что T ( n ) имеет порядок O ( n 2 ). ) В формулировке асимптотической оматики все члены исходного выражения оставляются с наибольшим вкладом при больших n (остальными членами можно пренебречь), а коэффициент перед ним игнорируется (поскольку все асимптотические значения выдаются с точностью до константы). При использовании обозначения O() имеют в виду не точное время выполнения, а лишь его верхнюю границу, с точностью до постоянного множителя. Например, когда говорят, что алгоритм требует времени порядка O(n2), имеют в виду, что время выполнения задачи не растет быстрее, чем квадрат числа элементов.