Poraba časa v odvisnosti od vhodnih podatkov

Doslej smo merili porabo časa na nekem konkretnem primerku našega problema – gledali smo tabelo a = [0, 1, ..., 99] in iskali vsoto s = 12345. Ni si težko predstavljati, da se čas izvajanja lahko spremeni, če našo funkcijo NajdiVsoto zaženemo na drugačnih vhodnih podatkih. Oglejmo si, na primer kaj se zgodi, če funkcijo zaženemo na vse večjih tabelah a:

Vaja

Izmeri čas izvajanja funkcije NajdiVsoto za naslednje vhodne podatke:

(1) a = [0, 1, 2, ..., 199] in s = 12345;
(2) a = [0, 1, 2, ..., 299] in s = 12345;
(3) a = [0, 1, 2, ..., 399] in s = 12345;
(4) a = [0, 1, 2, ..., 499] in s = 12345.

Izmerjeni čas nato vpiši v spodnjo tabelo.

Pri naših poskusih smo dobili naslednje rezultate:

Dolžina vhodne tabele	100	200	300	400	500
(a) Povprečni čas izvajanja [ms]	52	194	488	821	1308
(b) Tvoj povprečni čas izvajanja

Večji kot je primerek problema (v našem primeru to pomeni: daljša kot je tabela a), več časa funkcija porabi za njegovo obdelavo. To ni nič čudnega, pravzaprav bi bilo čudno, če ne bi bilo tako.

Zanimivo vprašanje pa je, kako hitro narašča čas izvajanja v odvisnosti od velikosti primerka problema (oz. z drugimi besedami, od velikosti vhodnih podatkov) – od tega je na primer odvisno, kako velike primerke problema bomo še lahko obdelali v nekem sprejemljivem času.

Čas izvajanja si zato lahko predstavljamo kot funkcijo T(n), pri čemer n pomeni velikost vhodnih podatkov. Pri naši nalogi z iskanjem vsot bi bilo za n smiselno uporabiti dolžino tabele a. Za naše dobljene meritve lahko funkcijo T(n) predstavimo z grafom takole:

Vaja

Izmeri čas izvajanja funkcije NajdiVsoto za naslednje vhodne podatke:

(1) a = [0, 1, 2, ..., 99] in s = 1234;
(2) a = [0, 1, 2, ..., 99] in s = 123;
(3) a = [0, 1, 2, ..., 99] in s = 12;
(4) a = [0, 15, 30, 45, ..., 15 * 99] in s = 1234.