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.