Naloga: časovna zahtevnost iskanja v urejeni tabeli

Iz MaFiRaWiki

Za iskanje elementa v linearno urejeni tabeli T[1:n] običajno uporabimo algoritem, ki temelji na metodi deli in vladaj in mu rečemo bisekcija.

  1. Napišite algoritem, ki reši omenjeni problem.
  2. Določite časovno zahtevnost tega algoritma.
  3. Pri določanju časovne zahtevnosti je ena ključnih predpostavk, da je za indeks i računanje vrednosti T[i] mogoče izvesti v konstantnem času.
  4. Algoritem sprogramirajte v kakšnem programskem jeziku, lahko pa uporabite tudi že vgrajeno rešitev.
  5. Ugotovite kako velika je še lahko tabele T, da je mogoče z vašim programom rešiti nalogo v razumnem času( npr. v petih minutah).
  6. Ali je omejitev čas ali prostor?
  7. S profiliranjem ugotovite, ali je pri velikih tabelah res mogoče računanje T[i] izvesti v konstantnem času.
Osebna orodja