полиномиальное время



Полиномиальный это

Автор Ёурик Комилов задал вопрос в разделе Другие языки и технологии

что такое Полиномиальный алгоритм? нужно короткое понятие Полиномиального алгорита и получил лучший ответ

Ответ от Женёк[гуру]
Если очень просто - Например тебе нужно перемножить 2 числа в которм н знаков. Помнишь детское умножение столбиком? Там от н зависит количество строк, которые нужно складывать.. . Т. е. если мы знаем входное н - (грубо говоря) количество данных, то знаем количество команд и время работы с точностью до коэффициента. Это и есть полиномиальный алгоритм.
Как вариант противоположности (чтобы ты понял) - закинь в программу рандом какой-нибудь и првяжи к нему какое-то серьёзное условие выполнения программы.. . Вот это уже не полином (полином= точное конечное время работы).

Ответ от Булат 1[гуру]
Алгоритм, время работы которого зависит от количества входных данных как полином, т. е. многочлен некоторой степени. Например, t = 3*N^3 + 4*N^2 + 8*N + 4.
Тут обычно пишут t = O(N^3).
Если вдаваться в подробности, нужно знать математику, а потом прочесть статью "вычислительная сложность" в википедии.

Ответ от 3 ответа[гуру]
Привет! Вот подборка тем с похожими вопросами и ответами на Ваш вопрос: что такое Полиномиальный алгоритм? нужно короткое понятие Полиномиального алгорита
Временная сложность алгоритма на Википедии
Посмотрите статью на википедии про Временная сложность алгоритма
Класс P на Википедии
Посмотрите статью на википедии про Класс P
Полиномиальная иерархия на Википедии
Посмотрите статью на википедии про Полиномиальная иерархия
 

Ответить на вопрос:

Имя*

E-mail:*

Текст ответа:*
Проверочный код(введите 22):*