Izziv 1 - Eksperimentalno določanje časovne zahtevnosti

Napišite program v programskem jeziku Java za empirično primerjavo dveh algoritmov za iskanje elementa v urejeni tabeli:

• navadnega zaporednega iskanja in

• dvojiškega iskanja.

Oba algoritma poženite večkrat za različne velikosti tabele. Pri tem izmerite in izračunajte povprečni čas iskanja elementa ter izpišite tabelo časov za oba algoritma.

Odgovorite: 

• Kateri algoritem je časovno učinkovitejši?

• Kako narašča čas iskanja za oba algoritma v odvisnosti od velikosti tabele?

• Kakšen bi bil idelaen algoritem?

• Katere so težave tovrstnega določanja časovne zahtevnosti?

Predlagamo, da izziv rešujete postopoma po naslednjih točkah.

a) Generiranje testnih primerov

Za generiranje testnih primerov napišite metodo, ki vam za podani n vrne (urejeno) tabelo celih števil z vrednostmi od 1 do n. Npr.

• int[] generateTable(int n)

b) Implementacija obeh algoritmov iskanja elementa

Napišite oba algoritma za iskanje elementa. Npr.

• int findLinear(int[] a, int v)
• int findBinary(int[] a, int l, int r, int v)

Pri tem je a tabela elementov, v iskana vrednost, l leva meja v tabeli in r desna meja v tabeli. Kakšno vrednost imata l in r ob prvem klicu findBinary(...)?

c) Izvedba ene meritve za tabelo velikosti n

Napišite metodi (za vsak način iskanja svojo metodo), ki izmerita povprečni čas iskanja v tabeli velikosti n. Npr.

• long timeLinear(int n)
• long timeBinary(int n)

Vsaka izmed metod naj izvede naslednje:

• Ustvari tabelo velikosti n z metodo, ki ste jo implementirali predhodno.
• Začne meriti čas.
• Nato 1000-krat ponovi naslednje
• Ustvari naključno število med 1 in n.
• Poišče število v tabeli.
• Ustavi merjenje časa.
• Izračuna povprečen čas iskanja števila

Čas izvajanja merite na sledeči način:

long startTime = System.nanoTime();
// iskanje elementa
long executionTime = System.nanoTime() - startTime;

d) Eksperimentalno ovrednotenje algoritmov

Za vrednosti \(n \in [20000,\dots,1000000]\) s korakom \(20000\) tabelirajte povprečni čas izvajanja. Izpišite tabelo s tremi stolpci:

• prvi stolpec naj vsebuje n,
• drugi povprečni čas izvajanja navadnega iskanja,
• tretji pa povprečni čas dvojiškega iskanja.

Primer izpisa:

   n       |     linearno  |   dvojisko  |
---------+--------------+------------------
    20000 |         20662 |           61
    40000 |         21444 |           66
    60000 |         22135 |           66
    80000 |         22706 |           67
    100000 |        23433 |           62
    120000 |        23751 |           71
      ...            ...              ...

e) Razmislite in odgovorite

• Zakaj so na časi pri vas drugačni kot v zgornji tabeli?
• Kateri algoritem je hitrejši?
• Kdaj bi lahko bil počasnejši algoritem hitrejši?
• Kako se čas iskanja odvisen od velikosti naloge (linearno, kvadratno, ...)?
• Je časovna odvisnost dvojiškega iskanja bližje linearni ali konstantni?
• Ali lahko napišemo boljši algoritem (za naš primer)?
• Katere so težave tovrstnega določanja časovne zahtevnosti?
• Kako jih skušamo zaobiti? 

Izvorno kodo, sliko tabele in odgovore stisnite v .zip datoteko oddajte na e-učilnici.

f) Grafični prikaz - neobvezno, a zabavno in poučno

Narišite graf zgoraj izmerjenih vrednosti časa izvajanja v odvisnosti od dolžine tabele. Za izris priporočamo uporabo knjižnice StdLib in razreda StdDraw. Za barvno izvedbo potrebujete dodati 6 vrstic v zgornjo rešitev.

V skrajni sili lahko uporabite tudi druge možnosti:

• Uporabite lahko program za izdelavo razpredelnic (OpenOffice, Excel, ...).
• Izris neposredno iz Jave z uporabo enostavne knjižnice jMathPlot. Na povezavi najdete enostaven uvod v uporabo te knjižnice.
• itd.