> собственно 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 Статус: Незарегистрированный пользователь
> тоесть если взять опр кол информации и опр алгоритм, > то полниномиальное время будет то, за которое этот > алгоритм эту информацию обработает ? так ? В принципе не совсем так.
Например алгоритм поиска значение в массиве - линейный, частный вид полиноминального (время зависит от длины). Во сколько раз размер массива больше, во столько раз и время поиска больше.
Нпример алгоритм сортировки - полиноминальный. В два раза массив больше - в четыре раза дольше будет выполняться сортировка.
Например алгоритм разложения числа на простые сомножители - экспоненциальный. В два раза больше разрядность числа (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 Статус: Незарегистрированный пользователь
подробно о проекте
Анализ криптографических сетевых...
новое сообщение
закрытая нитка
новое сообщение
в закрытой нитке
старое сообщение
