Złożoność obliczeniowa: Różnice pomiędzy wersjami
| [wersja przejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
m Wycofano edycje użytkownika 188.146.162.215 (dyskusja). Autor przywróconej wersji to Daroooo. Znacznik: Wycofanie zmian |
Korekcja interpunkcji. |
||
Linia 3:
'''Teoria złożoności obliczeniowej''' – dział [[teoria obliczeń|teorii obliczeń]], którego głównym celem jest określanie ilości zasobów potrzebnych do rozwiązania [[Problem obliczeniowy|problemów obliczeniowych]]. Rozważanymi zasobami są takie wielkości jak czas, pamięć lub liczba procesorów.
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 [[Rozkład na czynniki|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ć [[algorytm]]u rozwiązującego dany problem wraz z dowodem poprawności oraz opisem potrzebnych zasobów.
== Złożoność algorytmów ==
| |||