Aufgabenstellung: https://www.programmieraufgaben.ch/aufgabe/schraubensack/uk540btd

• Anzahl Zeilen in der Datei: $n$
• Kleinster und grösster Druchmesser: $d$ und $D$
• Anzahl verschiedene Durchmesser: $a$ (wobei $a<n$).

Eine Funktion $g(n)$ ist in $O(f(n))$ wenn es ein $n_0$ und $c_0$ gibt, so dass $$ g(n) < c_0 f(n) \qquad \forall n>n_0$$ Umgangssprachlich heisst das, die Funktion $g(n)$ wächst nicht schneller als $f(n)$.

Beispiel:

• Wenn $n$ Personen alle miteinander anstossen, macht es $O(n^2)$ mal “Kling”. (Natürlich auch $O(n^3)$, aber nicht $O(n)$)

Rechenaufwand:

• Sortieren $O(n \log(n))$ (naive Sortier-Algorithmen sind $O(n^2)$).
• Liste durchgehen $O(n)$

Insgesamt also $O(n \log(n))$.

Speicherplatz: $O(n)$ (die ganze Liste)

Rechenaufwand:

• (D-d) mal $n$ Einträge absuchen, also $O((D-d)\cdot n)$

Speicherplat: $O(n)$ (die ganze Liste)

Rechenaufwand:

• Nächsten Durchmesser finden:
  • Entweder Liste durchgehen, nächst-grösseren finden, also $O(n)$ pro Schritt.
  • Oder in der Liste weitersuchen, bis unbekannten Durchmesser gefunden, braucht aber $O(a)$ Speicherplatz. Insgesamt aber nur $O(n)$.
• Liste durchgehen, zählen: $O(n)$. Und das ganze $a$ mal.

Also total $O(a\cdot n \cdot n)$ = $O(n^2 a) \subset O(n^3)$ für die erste Variante.

Oder $O(a\cdot n + n) = O(a \cdot n) \subset O(n^2)$ für die zweite Variante.

Speicherplatz: $O(n)$ für beide Varianten (weil $O(n)=O(2n)$).

Rechenaufwand:

• Für jede Zeile, entsprechenden Eintrag finden: Wenn der Hash gut implementiert ist, $O(\log(a))$.

Also total $O(n \log(a)) \subset O(n \log(n))$.

Speicherplatz: $O(a)$ (Platz der Datei auf der Platte nicht mitgezählt).

schraubenback-bloechliger-mit-hash.rb

#!/usr/bin/ruby
data = Hash.new
File.open("schrauben.txt","r"){|f|
   while(line=f.gets) # Zeile einlesen
     was = line[0] == "m" ? 0 : 1
     d = line[2..-1].to_i
     unless data.has_key?(d)
        data[d] = [0,0]
     end
     data[d][was]+=1
   end
}
# Der folgende Sort ist O(a log(a)), was weniger
# als O(a log(a)) der obigen Schlaufe ist.
data.keys.sort.each{|d|
   puts "#{d}mm: #{data[d].min} passende Paare"
}