Teema: algoritmide keerukus


Millised oleksid järgmiste algoritmide keerukusklassid, milline ajaline keerukus parimal
ja halvimal juhul?

------------------------
/* Keskmise leidmine */
int sum = 0;
int i = 0;
for (i=0; i<n; i++) {
   sum += a[i];
}
return sum/n;

------------------------

/* Otsimine */
int a[n]; 
int x, leitud; (x on otsitav)
...
leitud = 0;
while (a[i] != x){
   if (a[i]==x)
       leitud = 1;
}
...
-------------------------

/* Sorteerimine - valikmeetodil (selection sort) */

for (i=0; i<n-1; i++) {
/* Kõigepealt leitakse vähim element listi osast x[i],...,x[n-1]. */
   pos= i;
   smallest = x[pos];
   for (j=i+1; j<n; j++) {
      if (x[j] < smallest) {
         pos= j;
         smallest = x[j];
      }
   } 
   x[pos] = x[i];
   X[i] = smallest
}

---------------------------

/* Sorteerimine (sama meetod) kas keerukus võrreldes eelmise algoritmiga on sama või teistsugune? 
   Milline? */

for (i=0; i<n-1; i++) {
/* funktsioon min() leiab massiivi vähima elemendi indeksi */
   pos = min(x[i..n-1]);
/* funktsioon swap() vahetab kahes muutujas väärtused */
   swap(x[pos];x[i]);
}


Kui aega jääb, vaatame ja käivitame programmid:
jada1_clockiga.c, jada2_clockiga.c: kasutame erinevaid andmehulki 1000, 10000, 100000.
jada3_clockiga.c: 1000, 2000, 3000