Полиномијално време
From Wikipedia, the free encyclopedia
From Wikipedia, the free encyclopedia
У теорији комплексности, полиномијално време се односи на време израчунавања проблема, где време, , није веће од полиномијалне функције величине проблема, . Математички записано у нотацији великог О, ово значи где је нека константа која може зависити од проблема. На пример, алгоритам за сортирање квиксорт за бројева захтева највише операција. Стога му је потребно време , па се ради о алгоритму полиномијалног времена.
Математичари некада користе појам полиномијалног времена у односу на дужину улаза као дефиницију брзог рачунања, као супротност супер-полиномијалном времену, које се односи на све шта је спорије од тога. Експоненцијално време је пример супер-полиномијалног времена.
Класа комплексности проблема одлучивања који могу бити решени детерминистичком Тјуринговом машином у полиномијалном времену је позната као класа П. Класа проблема одлучивања чије се потенцијално решење може проверити у полиномијалном времену је се назива класом НП. Еквивалентно, НП је класа проблема одлучивања који се могу решити у полиномијалном времену недетерминистичком Тјуринговом машином (НП значи Недетерминистичко Полиномијално време).
Алгоритми којима је потребно линеарно, логаритамско и константно време су бржи подскуп алгоритама који захтевају полиномијално време.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.