Есептеу күрделілігі теориясында көпмүшелік уақытты азайту бір мәселені басқа көмегімен шешу әдісі болып табылады. Көпмүшелік-уақыт қысқартулары күрделілік теориясында күрделілік кластарын да, сол сыныптар үшін толық есептерді де анықтау үшін жиі қолданылады. …
Көпмүшелік уақыт дегеніміз не?
Алгоритмнің орындалу уақыты алгоритм үшін кіріс өлшеміндегі көпмүшелік өрнекпен жоғарғы шектелген болса, алгоритм полиномды уақыт деп аталады, яғни T(n)=O(nk) кейбір оң тұрақты k үшін.
Бір нәрсенің көпмүшелік уақыт екенін қалай білуге болады?
3 Жауаптар. Кейбір k, C>0 үшін оның n өлшемді кірістердегі жұмыс уақыты ең көбі Cnk болса, алгоритм көпмүшелік болып табылады (полиномдық жұмыс уақыты бар). Баламалы түрде алгоритм көпмүше болады, егер кейбір k>0 үшін оның n өлшемді кірістердегі жұмыс уақыты O(nk) болса.
Егер қысқартуға экспоненциалды уақытта рұқсат берілсе не болады?
Егер қысқартуға экспоненциалды уақытқа рұқсат берілсе, онда ол бастапқы мәселені толығымен шеше алады және мақсатты мәселенің тривиальды данасын шығара алады Бұл NP-дегі әрбір мәселе әрбір мәселеге азайтылатынын білдіреді. қысқартулар түрі бойынша басқа мәселе, сондықтан NP ішіндегі әрбір мәселе экспоненциалды уақытты қысқарту үшін NP-толық болып табылады.
Көрсеткіштік алгоритм дегеніміз не?
Алгоритм экспоненциалды уақыт деп аталады, егер T(n) 2 арқылы жоғарғы шектелген болсаполи( ) , мұндағы поли(n) n-дегі кейбір көпмүшелік. Ресми түрде, T(n) кейбір тұрақты k үшін O(2nk) арқылы шектелген болса, алгоритм экспоненциалды уақыт болып табылады. Сілтеме:Wiki.
