Złożoność obliczeniowa
Z Wikipedii, wolnej encyclopedia
Teoria złożoności obliczeniowej – dział teorii obliczeń, którego głównym celem jest określanie ilości zasobów potrzebnych do rozwiązania problemów obliczeniowych. Rozważanymi zasobami są takie wielkości jak czas, pamięć lub liczba procesorów.
Zobacz też: Asymptotyczne tempo wzrostu (miara określającą zachowanie wartości funkcji wraz ze wzrostem jej argumentów, określana notacją dużego O). |
|
Ten artykuł od 2021-04 zawiera treści, przy których brakuje odnośników do źródeł. |
Za twórców tej teorii uważani są Juris Hartmanis i Richard Stearns. Jako przykłady problemów t.z.o. można podać problem spełnialności, problem najkrótszej ścieżki, problem faktoryzacji oraz wiele innych, o których wiadomo, że są obliczalne. Kwestią obliczalności zajmuje się teoria obliczalności, będąca drugą ważną gałęzią teorii obliczeń.
Wyniki, jakie podaje t.z.o., można podzielić na dwie kategorie: pozytywne i negatywne, czyli na takie, które podają, co i jak można obliczyć, oraz takie, w których dowodzi się, czego nie da się obliczyć, wykorzystując określoną ilość zasobów. Wyniki pozytywne są łatwiejsze do uzyskania i zwykle mają postać algorytmu rozwiązującego dany problem wraz z dowodem poprawności oraz opisem potrzebnych zasobów.