Zahlen sortieren < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:09 Do 11.12.2014 | | Autor: | evinda |
Hallo!!!
Ich will zeigen, dass man k ganze Zahlen mit Werte zwischen 0 und [mm] k^2-1 [/mm] in Zeit O(k) sortieren kann.
Könntet ihr mir ein Tipp geben wie man das machen könnte?
Ich habe die Frage auch in matheplanet gestellt: http://www.matheplanet.com/
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:37 Do 11.12.2014 | | Autor: | DieAcht |
Hallo evinda!
Tipp: Induktion!
Gruß
DieAcht
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 23:41 Do 11.12.2014 | | Autor: | evinda |
Wie benutzt man, wenn man Induktion macht, die Tatsache dass die Werte der ganzen Zahlen zwischen 0 und [mm] k^2-1 [/mm] sind?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 00:09 Fr 12.12.2014 | | Autor: | DieAcht |
Bist du dir sicher, dass du die Aufgabe verstanden hast?
Sei zum Beispiel [mm] $k=2\$, [/mm] dann gibt es in der Tat genau zwei Elemente
[mm] K_1\in\IZ [/mm] und [mm] K_2\in\IZ [/mm] mit [mm] $0
[mm] K_1,K_2\in\{1,2\}. [/mm] Wie können wir diese sortieren und
in welcher Zeit?
Jetzt überlegst du dir die Aussage für [mm] $k=3\$.
[/mm]
Am Besten du tippst auch die genaue Aufgabenstellung ein.
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 02:10 Fr 12.12.2014 | | Autor: | evinda |
> Bist du dir sicher, dass du die Aufgabe verstanden hast?
>
> Sei zum Beispiel [mm]k=2\[/mm], dann gibt es in der Tat genau zwei
> Elemente
> [mm]K_1\in\IZ[/mm] und [mm]K_2\in\IZ[/mm] mit [mm]0
> Offensichtlich sind das
> die Natürlichen Zahlen [mm]1\[/mm] und [mm]2\[/mm]. Wie können wir diese
> sortieren und
> in welcher Zeit?
Um diese Zeit zu finden, zählt man wie viele Vergleiche man machen muss? Falls ja, macht man nicht nur ein Vergleich?
> Jetzt überlegst du dir die Aussage für [mm]k=3\[/mm].
Dann hat man 3 natürliche Zahlen:
[mm] k_1 \in \{ 1,2,3,4,5,6,7 \}
[/mm]
[mm] k_2 \in \{ 1,2,3,4,5,6,7 \}
[/mm]
[mm] k_3 \in \{ 1,2,3,4,5,6,7 \}
[/mm]
Wie können wir die Zeit finden, die wir brauchen um diese Zahlen zu sortieren?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 02:20 Do 18.12.2014 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
