Кыскартуу полиномдук убакытпы?

2024 Автор: Fiona Howard | [email protected]. Акыркы өзгөртүү: 2024-01-10 06:40

Эсептөө татаалдыгы теориясында полиномдук убакытты кыскартуу бир маселени башка менен чечүү ыкмасы. Полиномдук убакыттын кыскартуулары татаалдык теориясында татаалдык класстарын да, ал класстар үчүн толук маселелерди да аныктоо үчүн көп колдонулат. …

Полиномдук убакыт деген эмне?

Алгоритмдин иштөө убактысы алгоритм үчүн киргизүүнүн өлчөмүндөгү полиномдук туюнтма менен жогору чектелсе, алгоритм полиномдук убакыт деп айтылат, башкача айтканда, T(n)=O(n^k) кээ бир оң туруктуу k.

Бир нерсенин полиномдук убакыт экенин кантип билесиз?

3 Жооптор. Эгерде кээ бир k, C>0 үчүн, n өлчөмүндөгү киргизүүлөр боюнча анын иштөө убактысы эң көп Cnk болсо, алгоритм полиномдуу (полиномдук иштөө убактысы бар). Эгер кээ бир k>0 үчүн, n өлчөмүндөгү киргизүүлөр боюнча анын иштөө убактысы O(nk) болсо, алгоритм эквиваленттүү болуп саналат.

Экспоненциалдык убакытта кыскартууга уруксат берилсе эмне болот?

Эгер кыскартууга экспоненциалдык убакытка уруксат берилсе, анда ал түпнуска маселени толугу менен чечип, максаттуу маселенин арзыбаган мисалын чыгара алат Бул NPдеги ар бир маселе ар бир маселеге кыскартыла турганын билдирет мындай кыскартуулар түрүндөгү башка маселе, ошондуктан NPдеги ар бир маселе экспоненциалдык убакытты кыскартуу үчүн NP-толук.

Экспоненциалдык алгоритм деген эмне?

Алгоритм экспоненциалдык убакыт деп айтылат, эгерде T(n) 2^{поли(менен жогорку чектелсе )} , мында poly(n) - n тилиндеги кээ бир көп мүчө. Эгер T(n) кандайдыр бир туруктуу k үчүн O(2^{nk) менен чектелген болсо, алгоритм экспоненциалдык убакыт болуп саналат. Ref:Wiki.}