1. Основные понятия алгоритмизации и программирования


Результат работы программы


Download 1.01 Mb.
bet71/78
Sana03.02.2023
Hajmi1.01 Mb.
#1148576
TuriЗадача
1   ...   67   68   69   70   71   72   73   74   ...   78
Bog'liq
c# qo\'llanma

4. Результат работы программы:
Введите элементы массива
1 2 3 4 -2 0 -3 -1 1 1 1 0
B 1-й строке 4 положительных элементов
B 2-й строке 0 положительных элементов
B 3-й строке 3 положительных элементов
Среднее арифметическое: 0.58

9. Алгоритмы решения задач внутренней сортировки и алгоритмы поиска информации

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


Теория сложности обеспечивает методологию анализа вычислительной сложности различных криптографических методов и алгоритмов.
Алгоритм – это формально описанная вычислительная процедура, получающая исходные данные, называемые также входом алгоритма или его аргументом, и выдающая результат вычислений на выход [4].
Чаще всего, говоря о сложности, имеют в виду временную сложность алгоритма: Т. Временем работы алгоритма называется число элементарных шагов, которые он выполняет. Под элементарными шагами понимают такие базисные операции, как сложение, умножение, замены, безусловные передачи управления и вызовы подпрограмм. Т обычно представляется в виде функции от п, где п - это размер входных данных. Функция времени вычисленийTA (n).
Обычно вычислительная сложность алгоритма выражается с помощью нотации "О большого", т.е описывается порядком величины вычислительной сложности. Это просто член разложения функции сложности, быстрее всего растущий с ростом n, все члены низшего порядка игнорируются. Например, если временная сложность данного алгоритма равна 4п2+7п+2, то вычислительная сложность порядка n 2, записываемая как О(п2) [4].
Эта нотация позволяет увидеть, как объем входных данных влияет на требования к времени и объему памяти. Например, если Т = О(п), то удвоение входных данных удвоит и время выполнения алгоритма. Если Т = О(2п), то добавление одного бита к входным данным удвоит время выполнения алгоритма.
Обычно алгоритмы классифицируются в соответствии с их временной или пространственной сложностью. Алгоритм называют постоянным, если его сложность не зависит от п: О(1). Алгоритм является линейным, если его временная сложность О(п). Алгоритмы могут быть квадратичными, кубическими и т.д. Все эти алгоритмы – полиномиальные, их сложность ­ О(пm), где m – константа. Алгоритмы с полиномиальной временной сложностью называются алгоритмами с полиномиальным временем.
Алгоритмы, сложность которых равна O(tf(n)), где t константа, большая, чем 1, a f(n)некоторая полиномиальная функция от n, называются экспоненциальными. Подмножество экспоненциальных алгоритмов, сложность которых равна О(с f(n)), где где с – константа, a f(n) возрастает быстрее, чем постоянная, но медленнее, чем линейная функция, называется суперполиномиальным. Алгоритмы, сложность которых равна O (n!), называются алгоритмами с факториальной сложностью. Таким образом, справедливо следующее соотношение:
(log n) < (n) < (log n) < O (n2) < O (n3) < O (2 n) < O (n!).
В настоящее время алгоритм считается практически полезным только в том случае, если его временная функция растет полиномиально относительно размеров входных данных, причем ограниченной степени. Практичными являются алгоритмы сложности (n), O (n2). Не практичны экспоненциальные и факториальные алгоритмы. Их сложность превосходит любую полиномиальную оценку.

Download 1.01 Mb.

Do'stlaringiz bilan baham:
1   ...   67   68   69   70   71   72   73   74   ...   78




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©fayllar.org 2024
ma'muriyatiga murojaat qiling