[infostudents] Algo: 1.2 (Gleiche X-koordinate == O(n^2)

  • From: Gökhan Özer <ozer@xxxxxxxxxxxxxxxxxxxxxxxxxx>
  • To: infostudents@xxxxxxxxxxxxx
  • Date: Mon, 27 Oct 2008 09:45:37 +0100

Hi,

Fall1: Gleiche X-Koordinate ---> O(n^2)

Da, angenommen folgende Punkte gegeben sind:
  • 2,2 und 4,2
  • 2,4 und 4,4
  • 2,6 und 4,6
  • 2,8 und 4,8
Die mindist ist hier 2, aber es werden alle Punkte miteinander verglichen.

Beim Devide kommt man ja am Ende auf 4 Teilmengen mit je 2 Elementen. Da die dist aber identisch ist, wird der Beobachtungsbereich "d" auf 2 gesetzt. Da aber alle Punkte von d genau "2" entfernt sind, werden nun alle Punkte miteinander verglichen. Das setzt sich  so bei jedem Mergeschritt fort, und man erhält am ende eine Laufzeit von O(n^2).. :(

Es ist anschaulicher, wenn ihr euch die Punkte kurz aufzeichnet!
-- 
Gökhan Özer
Colombistrasse 17
789098 Freiburg
Matrikel Nr.: 1302829
Tel: 0176-21969169
--- Sent through the Infostudents Mailinglist List Archive: //www.freelists.org/archives/infostudents/ Subscribe / Unsubscribe: //www.freelists.org/list/infostudents

Other related posts:

  1. Home
  2. infostudents
  3. Archive
  4. 10-2008