Kazalo:
Opredelitev - Kaj pomeni časovna zapletenost?
Časovna zapletenost je koncept v računalniški znanosti, ki se ukvarja s količinsko določitvijo časa, ki ga porabi niz kode ali algoritma za obdelavo ali zagon kot funkcijo količine vnosa.
Z drugimi besedami, časovna zapletenost je v bistvu učinkovitost ali kako dolgo programska funkcija traja za obdelavo danega vnosa.
Tehopedija razlaga časovno zapletenost
Časovna zapletenost je preprosto merilo časa, potrebnega za funkcijo ali izraz, da opravi svojo nalogo, pa tudi ime postopka za merjenje tega časa. Uporablja se lahko za skoraj vsak algoritem ali funkcijo, vendar je bolj uporaben za rekurzivne funkcije. Malo je smiselno meriti časovno zahtevnost aplikacij, na primer pridobivanje uporabniškega imena in gesla iz baze podatkov za primerjavo ali preprosto shranjevanje podatkov, ne glede na to, ali je 20 ms ali 5 ms; to bi bilo več v vrstici dostopa. To nima nobene zveze s skrbjo o času izvršitve, temveč je razlika zanemarljiva. Če pa obstaja rekurzivna funkcija, ki jo lahko kličemo večkrat, lahko določitev in razumevanje vira njene časovne zapletenosti skrajša čas celotne obdelave s, recimo, 600 ms na 100 ms.
Časovna zapletenost je navadno izražena v "velikem O notaciji", obstajajo pa tudi drugi zapisi. To je matematični prikaz zgornje meje faktorja skaliranja za algoritem in je zapisan kot O (Nn), pri čemer je "N" število vhodov in "n" število izrazov z zanko. Na primer, algoritem:
numbers = {5, 6, 10, 11, 2}; foreach (number as number1)
{
foreach(number as number2)
{
statements; } }
numbers = {5, 6, 10, 11, 2};
foreach (number as number1)
{
foreach(number as number2)
{
statements; } }
numbers = {5, 6, 10, 11, 2};
foreach (number as number1)
{
foreach(number as number2) {
statements; } }
numbers = {5, 6, 10, 11, 2};
foreach (number as number1)
{
foreach(number as number2)
{
statements; } }
numbers = {5, 6, 10, 11, 2};
foreach (number as number1)
{
foreach(number as number2)
{
statements; } }
V nizu "številk" je pet vhodov, zanka "foreach" pa se ponovi dvakrat. Zato se eksponentna rast časa obdelave pojavlja, ko narašča število vhodov in število zank.
