Subato

Resource Files

HasDups

Gegeben sei ein aufsteigend sortiertes Array xs, bestehend aus n Zahlen.
Betrachten Sie folgenden Algorithmus:
procedure HasDups(xs, n)
  for i = 0, ..., n-1 do
    if LinearSearch(xs, n, i+1, xs[i]) then return true
  return false

procedure LinearSearch(xs, n, start, value)
  j ← start
  while j < n do
    if xs[j]==value then return true
    j ← j+1
  return false
  • Implementieren Sie den Algorithmus für int-Arrays in Java und ermitteln Sie jeweils die Laufzeit, indem Sie Ihr Programm ausführen. Verwenden Sie als Eingabe Arrays der Länge n = 1.000, 10.000, 100.000 und 200.000. Wählen Sie die Arrays so, dass die maximale Anzahl an Rechenschritten benötigt wird. Hinweis: Ihre Messwerte müssen Sie nicht in subato abgeben. Bringen Sie sie einfach mit ins Praktikum.
  • Können Sie aus Ihren Messwerten die Worst-Case-Komplexitätsklasse Ihres Verfahrens schätzen?
  • Entwickeln Sie ein Verfahren mit günstigerer Komplexität und begründen Sie, warum nun eine günstigere Komplexitätsklasse vorliegt. (Hinweis: Nutzen Sie die Tatsache dass das Array vollständig sortiert ist. Können Sie sich nun die volle Suche durch das restliche Array in LinearSearch() sparen?). Implementieren Sie diese Variante, und schätzen Sie erneut die Komplexität anhand ihrer Messwerte.

package de.hsrm.cs.ads; public class HasDups { static boolean hasDups(int[] xs) { return false; } private static boolean linearSearch(int[] xs, int start, int v) { return false; } static boolean hasDupsFaster(int[] xs) { return false; } // as requested on the exercise sheet, we // run a duplicate check and record runtime. public static void runTest(int[] xs) { boolean result; long startTime; long endTime; // run slow version startTime = System.currentTimeMillis(); result = hasDups(xs); endTime = System.currentTimeMillis(); System.out.format( "[QUADRATIC] %d values: %d ms. Found duplicate? %b\n", xs.length, (endTime - startTime), result); // run fast version startTime = System.currentTimeMillis(); result = hasDupsFaster(xs); endTime = System.currentTimeMillis(); System.out.format( "[LINEAR] %d values: %d ms. Found duplicate? %b\n", xs.length, (endTime - startTime), result); } }
java
You are not logged in and therefore you cannot submit a solution.