Daten
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$).
$O(f(n))$ Notation
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)$)
Sortieren, zählen
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)
Durchmesser sequentiell durchgehen, Liste danach absuchen
Rechenaufwand:
- (D-d) mal $n$ Einträge absuchen, also $O((D-d)\cdot n)$
Speicherplat: $O(n)$ (die ganze Liste)
Nur vorhandene Durchmesser durchgehen
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)$).
Mit Hash
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" }