Легенда:
 новое сообщение
 закрытая нитка
 новое сообщение
 в закрытой нитке
 старое сообщение
|
- Напоминаю, что масса вопросов по функционированию форума снимается после прочтения его описания.
- Новичкам также крайне полезно ознакомиться с данным документом.
Господа, будьте снисходительны, не бросайтесь сразу штрафовать за, как вам кажется, глупые вопросы - beginners на то и beginners.
| |
немного не так.. 10.03.04 07:34 Число просмотров: 1059
Автор: zelych Статус: Member
|
функция f(n) - функция полиномиального роста, если существует d = const, при любых n выполняется неравенство f(n) <= n^d
время выполнения t(n) - максимальное количество тактов (по всем входам длины n), требуемое для получения результата
складываем, получаем...
п.с. n - длина входа алгоритма
|
|
<beginners>
|
полиномиальное время 09.03.04 23:59
Автор: OKO Статус: Незарегистрированный пользователь
|
собственно subj
у меня есть конечно догадки что это большой промежуток времени,
но я что-то не уверен :)
кто знает подскажите
зарание благодарен
|
|
Это зависимость скорости алгоритма от размера входных данных 10.03.04 00:12
Автор: whiletrue <Роман> Статус: Elderman
|
> собственно subj
> у меня есть конечно догадки что это большой промежуток
> времени,
> но я что-то не уверен :)
>
> кто знает подскажите
> зарание благодарен
Это всего лишь значит, что зависимость скорости алгоритма от размера входных данных - полиномиальная, т.е. существует полином p, такой что при входных данных размером n, данный алгоритм гарантировано остановится через p(n) шагов.
|
| |
немного не так.. 10.03.04 07:34
Автор: zelych Статус: Member
|
функция f(n) - функция полиномиального роста, если существует d = const, при любых n выполняется неравенство f(n) <= n^d
время выполнения t(n) - максимальное количество тактов (по всем входам длины n), требуемое для получения результата
складываем, получаем...
п.с. n - длина входа алгоритма
|
| |
тоесть если взять опр кол информации и опр алгоритм,
10.03.04 00:21
Автор: OKO Статус: Незарегистрированный пользователь
|
тоесть если взять опр кол информации и опр алгоритм,
то полниномиальное время будет то, за которое этот алгоритм эту информацию обработает ? так ?
|
| | |
В принципе не совсем так. 10.03.04 11:48
Автор: DPP <Dmitry P. Pimenov> Статус: The Elderman
Отредактировано 10.03.04 11:51 Количество правок: 1
|
> тоесть если взять опр кол информации и опр алгоритм,
> то полниномиальное время будет то, за которое этот
> алгоритм эту информацию обработает ? так ?
В принципе не совсем так.
Например алгоритм поиска значение в массиве - линейный, частный вид полиноминального (время зависит от длины). Во сколько раз размер массива больше, во столько раз и время поиска больше.
Нпример алгоритм сортировки - полиноминальный. В два раза массив больше - в четыре раза дольше будет выполняться сортировка.
Например алгоритм разложения числа на простые сомножители - экспоненциальный. В два раза больше разрядность числа (256 вместо 128), а операций приблизительно больше на 2^256-2^128 больше или в 2^128 раз.
|
| | |
еще бывает... 10.03.04 09:35
Автор: whiletrue <Роман> Статус: Elderman
Отредактировано 10.03.04 09:37 Количество правок: 1
|
> тоесть если взять опр кол информации и опр алгоритм,
> то полниномиальное время будет то, за которое этот
> алгоритм эту информацию обработает ? так ?
еще бывает линейное, экспоненциальное, ... этохарактеристикасложности алгоритма.
"...Простые задачи (решаемые) – задачи, решаемые за полиномиальное время (например решение СЛУ в рациональных числах)
Сложные задачи (трудные, не решаемые) – задачи, которые не решаются за полиномиальное время, либо алгоритм решения за полиномиальное время не найден..."
|
| | |
В принципе правильно 10.03.04 03:05
Автор: amirul <Serge> Статус: The Elderman
|
> тоесть если взять опр кол информации и опр алгоритм,
> то полниномиальное время будет то, за которое этот
> алгоритм эту информацию обработает ? так ?
Но все-таки счет ведется как и было сказано на ОПЕРАЦИИ. Причем чаще всего сложения/вычитания/сравнения и пр.. Если задать время выполнения каждой операции, то такой полином легко преобразовывается во время (но не наоборот)
|
| | | |
ок,спасибо большое , а то не мог инфы найти ,да и... 10.03.04 13:05
Автор: OKO Статус: Незарегистрированный пользователь
|
|
ок,спасибо большое , а то не мог инфы найти ,да и растолковать было некому :)
|
|
|
подробно о проекте
Анализ криптографических сетевых...
