Seiten

  • Startseite
  • Impressum
  • Inhalt
  • MINT
  • Sprache
  • Soziales
  • Geist
  • Kunst
  • Gemischtes
  • Gedichte

Freitag, 9. Januar 2015

Minimum- und Maximumfunktion


Deutsch

Die herkömm­li­che Me­tho­de, um das Mi­ni­mum ei­ner Lis­te gan­zer Zah­len zu be­rech­nen:

private static Integer min(List<Integer> array){
 Integer min = Integer.MAX_VALUE;
 for(Integer i : array){
  if(i < min){
   min = i;
  }
 }
 return min;
}


Ich ha­be mich ge­fragt, ob es schnel­ler geht, wenn man einen Al­go­rith­mus be­nutz, der kei­ne Ver­glei­che durchführt, son­dern das Mi­ni­mum re­kur­siv be­rech­net. Er sah dann wie folgt aus:

private static Integer min(List<Integer> array){
 try {
  Integer a = array.get(0);
  array.remove((int) 0);
  Integer b = min(array);
  return (a+b-Math.abs(a-b))/2;
 }
 catch(IndexOutOfBoundsException e){
  return Integer.MAX_VALUE;
 }
}


Die­sem Al­go­rith­mus liegt die Be­rech­nung des Mi­ni­mums zwei­er Zah­len zu­grun­de: min(a,b)=(a+b-|a-b|)/2.

Mit ein paar Abände­run­gen ist die­ser Kode auch zum Be­rech­nen ei­nes Ma­xi­mums taug­lich.

Al­ler­dings ist die Lauf­zeit mei­nes Al­go­rith­mus höher als die der Stan­dard­va­ri­an­te (im Praxis­test ge­mes­sen).

Spaßfakt: Das Wort Al­go­rith­mus lei­tet sich von Al-H̲wa­rizmī, dem Na­men ei­nes per­sisch-ara­bi­schen Ma­the­ma­ti­kers, ab. (vgl. Du­den)

Kommentare:

  1. Reine Interessensfrage: Brauchst du das für dein Studium oder hattest du einfach Lust dich damit zu beschäftigen?

    AntwortenLöschen
    Antworten
    1. Haha, wenn mein Studium nur auf diesem Niveau stattfinden würde! -- Nein, so was geht mir zwischendurch durch den Kopf.

      Löschen