Oppgave 1

I dette faget vil i hvert fall flg. sorteringsmetoder bli tatt opp (det finnes mange flere):

Oppgave 2

Regnskapet sier at antallet grunnleggende operasjoner er 5n + x der x er antallet ganger sammenligningen a[i] > a[m] er sann. Med de 10 verdiene 10, 5, 7, 2, 9, 1, 3, 8, 4, 6 vil sammenligningen aldri bli sann siden den største ligger først, dvs. x = 0. Dermed blir det utført 5·10 = 50 grunnleggende operasjoner.

Oppgave 3

Her blir x = 9 og dermed 5·10 + 9 = 59 grunnleggende operasjoner.

Oppgave 4

Her blir x = 4 og dermed 5·10 + 4 = 54 grunnleggende operasjoner.

Oppgave 5

Første versjon av metoden minmaks benytter at vi på forhånd har metoder maks og min som finner størst og minst verdi i en tabell.

  public static int[] minmaks(int[] a)
  {
    return new int[]{min(a),maks(a)};
  }

Den første versjonen utfører alltid 2n − 2 sammenligninger siden maks-metoden og min-metoden hver for seg ufører n − 1 sammenligninger.

Neste versjon av minmaks er hårfint mer effektiv:

  public static int[] minmaks(int[] a)
  {
    int mi = 0, minverdi = a[0];
    int ma = 0, maksverdi = a[0];

    int verdi = 0;

    for (int i = 1; i < a.length; i++)
    {
      verdi = a[i];

      if (verdi > maksverdi) { maksverdi = verdi; ma = i;}
      else if (verdi < minverdi) {minverdi = verdi; mi = i;}
    }

    return new int[]{mi,ma};
  }  

Testen verdi > maksverdi utføres n − 1 ganger. Hver gang den ikke er sann blir også testen verdi < minverdi utført. Det viser seg (se Avsnitt 1.1.6) at sammenligningen verdi > maksverdi er sann gjennomsnittlig få ganger og dermed usann de fleste gangene. Dermed får vi et gjennomsnittlig antall sammenligninger i metoden over som bare er marginalt mindre enn 2n − 2.

Det verste tilfellet får vi når den største ligger først. Fortsatt vil verdi > maksverdi bli utført hver gang, og den er usann hver gang. Dermed blir også verdi < minverdi utført hver gang. Tilsammen 2n - 2 sammenligninger i det verste tilfellet.

Det er mulig å lage en en algoritme som bruker ca. 1.5n sammenligninger. Men da må det isteden foretas en del ombyttinger i tabellen og kostnadene ved det er nok større enn det en tjener på å ha færre sammenligninger. Se Oppgave 1 i Avsnitt 1.2.14 i Delkapittel 1.2.

Oppgave 6

  public static long fak(int n)
  {
    if (n < 0)
      throw new IllegalArgumentException("n < 0");
    long fak = 1;

    for (int i = 2; i <= n; i++) fak *= i;

    return fak;
  }

Hvis n = 0 eller 1 utføres ingen multiplikasjoner. Hvis n > 1 utføres det n − 1 multiplikasjoner.