| Attributes | Values |
|---|
| rdfs:label
| - Угловая мера асимптотического роста функций и ее свойства
|
| rdfs:comment
| - Отыскание функций сложности алгоритмов важно как с теоретической, так и с практической точек зрения. С теоретической точки зрения интересен вопрос: как далеко для данной задачи можно продвигаться по пути уменьшения сложности алгоритмов ее решения. С практической точки зрения важен порядок роста функции сложности t(n) c возрастанием параметра n. Действительно, на практике нет необходимости в точном построении выражения для функции сложности, что зачастую выполнить непросто. Использование приближенного представления оправдано тем, что возникающей ошибкой можно пренебречь. На практике применяют асимптотические оценки функций сложности.
|
| dcterms:subject
| |
| dbkwik:ru.science/...iPageUsesTemplate
| |
| abstract
| - Отыскание функций сложности алгоритмов важно как с теоретической, так и с практической точек зрения. С теоретической точки зрения интересен вопрос: как далеко для данной задачи можно продвигаться по пути уменьшения сложности алгоритмов ее решения. С практической точки зрения важен порядок роста функции сложности t(n) c возрастанием параметра n. Действительно, на практике нет необходимости в точном построении выражения для функции сложности, что зачастую выполнить непросто. Использование приближенного представления оправдано тем, что возникающей ошибкой можно пренебречь. На практике применяют асимптотические оценки функций сложности. Традиционная классификация алгоритмов основана на асимптотических оценках их функций сложности, причем в качестве разделяющей взята степен-ная функция с неотрицательным казателем. Такое разграничение позволяет выделить низкозатратные (с точки зрения вычислительных ресурсов) – полиномиальные алгоритмы и высокозатратные – экспоненциальные алгоритмы. Сегодняшнее время стремительного развития вычислительной техники и информационных технологий диктует необходимость более детального разграничения сложностных классов алгоритмов. Так, в криптографических системах широкое практическое применение уже находят субэкспоненциальные алгоритмы – алгоритмы с более чем полиномиальной, но менее чем экспоненциальной сложностью. В настоящее время широкое применение получили алгоритмы функция сложности которых растет медленнее чем у полиномов. Так же следовало бы выделить класс алгоритмов функция сложности которых растет намного быстрее чем у экспоненты. Для теории алгоритмов желательно, чтобы новая классификация алгоритмов не разрушала традиционной, а лишь дополняла и уточняла ее – позволяла бы выделить субполиномиальные, субэкспоненциальные и гиперэкспо-ненциальные алгоритмы. При этом классификационный признак должен быть хорошо вычисляем для наиболее типичных функций сложности. Известны попытки введения детальной классификации алгоритмов, удовлетворяющей указанным требованиям. Например, Головешкин В.А. и Ульянов М.В. предложили в качестве классификационного признака использовать значение угловой меры асимптотического роста функций сложности.
|
| is wikipage disambiguates
of | |
![[RDF Data]](/fct/images/sw-rdf-blue.png)