|
| |
|
|
Ответов: 0
|
25-02-12 07:01
|
|
|
| |
|
|
Ответов: 0
|
16-01-12 20:13
|
|
|
| |
|
|
Ответов: 1
|
09-01-12 11:23
|
|
|
Возможно вас заинтересует
|
|
Оценка сложности алгоритмов
С каждым алгоритмом обычно связывается интуитивное представление о их сложности, основанное на оценке количества необходимых преобразований слов, а также количества и длины самих слов. Однако, интуитивное представление не позволяет однозначно выбрать для решения конкретной задачи один из множества эквивалентных алгоритмов или определить возможность применения данного алгоритма для ее решения. При формальной оценке сложности алгоритмов можно использовать следующие определения.
Пусть:
- А – алгоритм решения некоторого класса задач и n-размерность одной задачи из этого клааса (в частном случае n может быть, например длинной последовательности в рассмотренном выше алгоитме, количеством слов в анализируемом тексте и т.п.);
- функция fA(n) даст верхнюю границу для максимального числа основных операций, которые должен выполнить алгоритм А для решения любой задачи размерности n.
Тогда алгоритм называется полиномиальным, если fA(n) растет не быстрее чем полином от n. В противном случае алгоритм А называется экспоненциальным. Так, функции типа kn, kn2,kn3,..., где k – коэфициент, могут рассматриваться как полиномиальные, а функции типа 2n, nn, n!... как экспоненциальнные.
Для достаточно больших n значение экспоненциальной функции всегда превышает значение полиномиальной функции. Для малых n это не всегда справедливо, но всегда есть такое n, для которого значение экспоненциальной функции превышает аналогичное для полиномиальной.
Время, затраченное на реализацию алгоритма, как функция размерности задачи называется временной сложностью алгоритма и обозначается как O[fA(n)]. Применительно к решению задачи на ЭВМ это время является в большинстве случаев свойством самого алгоритма и слабо зависит от машины, на которой решается соотвтствующая алгоритму программа.
Кроме временной сложности алгортмов существуют и другие меры сложности. Так, сложность можно характиризовать числом операций N (применительно к конкретной ЭВМ) и общим объемом информации Р, т.е общим количеством слов, используемых при выполнении алгоритма. Тогда время его выполнения на конкретной ЭВМ связано с числом операций, а объем информации связан с объемом памяти, необходимой машине для реализации соответствующей программы. Следовательно, время реализации алгоритма есть функция T=f(N). При таком подходе значения Т и Р называют соответственно вычислительной и емкостной сложностью алгоритма.
|
Последние статьи: Программирование под ОС / Алгоритмы /
| |
| | |
|
Алгоритмом часто называют конечную совокупность инструкций для решения некоторого класса задач. Это определение неформально, так как с его помощью нельзя однозначно ответить на вопросы, что такое совокупность инструкций и некоторый класс задач... подробнее
|
|
Кол. просмотров: общее - 3811 сегодня - 0
|
|
|
В современной математике алгоритмами принято называть конструктивно задаваемые соответствия между словами в абстрактных алфавитах. Это определение, в свою очередь, использует два понятия – понятие абстрактного алфавита и слов в таком алфавите... подробнее
|
|
Кол. просмотров: общее - 3807 сегодня - 1
|
|
|
К наиболее простым алфавитным операторам относятся так называемые посимвольные отображения. Последнее состоит в том, что каждый символ входного слова алфавита А заменяется некоторым символом выходного алфавита В... подробнее
|
|
Кол. просмотров: общее - 3830 сегодня - 1
|
|
|
Понятие алфавитного оператора является чрезвычайно общим. К нему фактически сводятся или могут быть сведены любые процессы преобразования информации, поскольку символам алфавита можно поставить в соответствие объекты произвольной природы... подробнее
|
|
Кол. просмотров: общее - 3616 сегодня - 0
|
|
|
С каждым алгоритмом обычно связывается интуитивное представление о их сложности, основанное на оценке количества необходимых преобразований слов, а также количества и длины самих слов... подробнее
|
|
Кол. просмотров: общее - 3724 сегодня - 0
|
|
|
|
