Złożoność obliczeniowa: Różnice pomiędzy wersjami

{{Inne znaczenia|2='''[[Asymptotyczne tempo wzrostu]]''' (miara określającą zachowanie wartości funkcji wraz ze wzrostem jej argumentów, określana '''notacją dużego O''')}}

'''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.

 

 

== Złożoność algorytmów ==

 

Przykładowo można by rozpatrzyć rozkład liczb na czynniki pierwsze. Przewidzieć można, że (niezależnie od zastosowanego algorytmu) im większa liczba, tym więcej zasobów będzie potrzebnych do jej rozłożenia. Tę cechę podziela większość zagadnień obliczeniowych – im większe rozmiary danych wejściowych, tym więcej zasobów (czasu, procesorów, pamięci) jest koniecznych do wykonania danych obliczeń. Złożoność algorytmu jest więc [[Funkcja|funkcją]] rozmiaru danych wejściowych.