verfahren, zeitkomplexität < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 20:44 Di 10.11.2009 | | Autor: | den9ts |
| Aufgabe | Betrachten Sie ein zwei-dimensionales Feld L[i][j] mit Indizies i, j [mm] \in [/mm] {1, . . . ,m}, das bei Konstanthalten eines Index bezüglich des anderen Index geordnet ist. Für alle i, j, k, l [mm] \in [/mm] {1, . . . ,m} gelte also
1. L[i][j] [mm] \le [/mm] L[k][j], wenn i < k, und
2. L[i][j] [mm] \le [/mm] L[i][l], wenn j < l.
Gegeben sei ein Verfahren, das ein solches Feld L und einen Schlüssel s als Eingabe erhält und feststellt, ob s in L enthalten ist. Leiten Sie eine untere Schranke der Zeitkomplexität für ein solches Verfahren her. Gibt es ein Verfahren mit Zeitaufwand in O(logm)? |
hej, hab leider garkein plan von der aufgabe und hoffe mir kann jmd helfen mich in die richtige richtung zu führn
also ich soll eine untere schranke herleiten (d.h. herleiten wieviel schritte der algorithmus mindestens ausführen muss, bis der schlüssel gefunden wird ( bzw um das Problem zu lösen))
speziell bei der 2 dimensionalen liste muss sich der algorithmus sich im durchschnitt ca. die hälfte aller felder anschauen um den schlüssel zu finden?
bei m feldern je liste ergibt das m*m verschiedene felder, d.h. im durchschnitt muss sich der algorithmus [mm] \bruch{(m*m)}{2} [/mm] felder anschauen?
das würde [mm] O(m^2) [/mm] entsprechen?
so wärn jetz meine gedanken zu der aufgabe gewesen, aber glaub das is nich so knorke...
danke
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 02:59 Mi 11.11.2009 | | Autor: | felixf |
Hallo!
> Betrachten Sie ein zwei-dimensionales Feld L[j] mit
> Indizies i, j [mm]\in[/mm] {1, . . . ,m}, das bei Konstanthalten
> eines Index bezüglich des anderen Index geordnet ist. Für
> alle i, j, k, l [mm]\in[/mm] {1, . . . ,m} gelte also
> 1. L[j] [mm]\le[/mm] L[k][j], wenn i < k, und
> 2. L[j] [mm]\le[/mm] L[l], wenn j < l.
>
> Gegeben sei ein Verfahren, das ein solches Feld L und einen
> Schlüssel s als Eingabe erhält und feststellt, ob s in L
> enthalten ist. Leiten Sie eine untere Schranke der
> Zeitkomplexität für ein solches Verfahren her. Gibt es
> ein Verfahren mit Zeitaufwand in O(logm)?
> hej, hab leider garkein plan von der aufgabe und hoffe mir
> kann jmd helfen mich in die richtige richtung zu führn
>
> also ich soll eine untere schranke herleiten (d.h.
> herleiten wieviel schritte der algorithmus mindestens
> ausführen muss, bis der schlüssel gefunden wird ( bzw um
> das Problem zu lösen))
Genau.
> speziell bei der 2 dimensionalen liste muss sich der
> algorithmus sich im durchschnitt ca. die hälfte aller
> felder anschauen um den schlüssel zu finden?
Nein, sicher nicht. Mir faellt spontan ein Algorithmus ein, der das Problem in [mm] $\mathcal{O}(m \log [/mm] m)$ Schritten loest, also weniger also [mm] $\Omega{O}(m^2)$ [/mm] Schritte braucht die du als untere Schranke haben willst.
Du kannst weiterhin recht einfach zeigen, dass es keinen Algorithmus geben kann, der dieses Problem in weniger als [mm] $\Omega(m)$ [/mm] Schritten loesen kann. Zeige dazu, dass du eine beliebige Folge [mm] $(a_1, \dots, a_m)$ [/mm] aus [mm] $\{ 1, \dots, m + 1 \}$ [/mm] in so ein Schema einbetten kannst, und ein Algorithmus der testet ob ein Element in dem Schema liegt entscheidet, ob eins der [mm] $a_i$ [/mm] gleich 1 ist. (Da die [mm] $a_i$ [/mm] beliebig sein koennen kann man sich leicht ueberlegen, dass jeder solche Algorithmus im worst case $m$ Schritte braucht.)
LG Felix
|
|
|
|
