Frage zu heapsort
-
blurry3333 schrieb:
Hallo,
welchen Sinn macht denn dieser heapsort überhaupt ?
Schließlich muss man das array welches sortiert werden soll , zuerst
in einen max heap überführen. Dies dauert doch schon eine ganze Weile.
Wo soll da noch der Performance Vorteil liegen ?Das Überführen in den Heap ist AFAIK sowieso das, was am wenigsten Zeit braucht (jedenfalls bei meiner Implementation). Welchen Sinn macht Slowsort überhaupt?
-
wxSkip schrieb:
Welchen Sinn macht Slowsort überhaupt?
Kannst du doch nachlesen:
http://de.wikipedia.org/wiki/Slowsort
-
drakon schrieb:
wxSkip schrieb:
Welchen Sinn macht Slowsort überhaupt?
Kannst du doch nachlesen:
http://de.wikipedia.org/wiki/SlowsortIch finde keinen Sinn außer dem wissenschaftlichen Witz.
-
wxSkip schrieb:
drakon schrieb:
wxSkip schrieb:
Welchen Sinn macht Slowsort überhaupt?
Kannst du doch nachlesen:
http://de.wikipedia.org/wiki/SlowsortIch finde keinen Sinn außer dem wissenschaftlichen Witz.
Dann ist Bogosort wohl auch nichts fuer dich
-
Shade Of Mine schrieb:
wxSkip schrieb:
drakon schrieb:
wxSkip schrieb:
Welchen Sinn macht Slowsort überhaupt?
Kannst du doch nachlesen:
http://de.wikipedia.org/wiki/SlowsortIch finde keinen Sinn außer dem wissenschaftlichen Witz.
Dann ist Bogosort wohl auch nichts fuer dich
kann sich mal einer melden, der Bogosort in seinen Programmen benutzt?
-
Abgesehen davon, dass es, wie du sagst mehr als Witz gedacht ist, kann man da halt sehr schön mal andere Laufzeitkomplexitäten sehen und mal ein wenig vergleichen mit realen Algorithmen.
Bogosort finde ich irgendwie noch nett.
-
Da fällt mir eine schöne schwierige Aufgabe ein:
Programmiere einen Algorithmus mit O(n^3.14) Laufzeit
-
Irgendeinen Algorithmus, oder einen Sortieralgorithums?
-
wxSkip schrieb:
Da fällt mir eine schöne schwierige Aufgabe ein:
Programmiere einen Algorithmus mit O(n^3.14) LaufzeitIch bin dann mal so frei, sogar einen Sortieralgorithmus zu wählen. Pseudocode:
- N Elemente mit O(N*log(N)) sortieren.
- N^3.14 Sekunden warten
- Fertig!
-
SeppJ schrieb:
wxSkip schrieb:
Da fällt mir eine schöne schwierige Aufgabe ein:
Programmiere einen Algorithmus mit O(n^3.14) LaufzeitIch bin dann mal so frei, sogar einen Sortieralgorithmus zu wählen. Pseudocode:
- N Elemente mit O(N*log(N)) sortieren.
- N^3.14 Sekunden warten
- Fertig!
War nur als Scherz gedacht, aber gut!
-
drakon schrieb:
Irgendeinen Algorithmus, oder einen Sortieralgorithums?
Ist mir eigentlich egal.
-
wxSkip schrieb:
Da fällt mir eine schöne schwierige Aufgabe ein:
Programmiere einen Algorithmus mit O(n^3.14) LaufzeitGegeben sei folgendes Spiel für eine Person:
Der Spieler startet mit 0kg Uran. Zu Anfang seines Zuges bekommt er PI kg Uran hinzu.
Er muß daraus so viele Atombomben zu je 1kg Uran bauen, wie möglich.
Im ersten Zug also 3 Bomben (Rest 0.14kg), im zweiten Zug weitere 3 Bomben (Rest 0.28kg), im dritten ...Zug Anfang Bomben Ende 1 3,14 3 0,14 2 3,28 3 0,28 3 3,42 3 0,42 4 3,56 3 0,56 5 3,7 3 0,7 6 3,84 3 0,84 7 3,98 3 0,98 8 4,12 4 0,12 9 3,26 3 0,26 10 3,4 3 0,4 11 3,54 3 0,54 12 3,68 3 0,68 13 3,82 3 0,82 14 3,96 3 0,96 15 4,1 4 0,1 16 3,24 3 0,24 17 3,38 3 0,38 18 3,52 3 0,52 19 3,66 3 0,66 20 3,8 3 0,8Er muß pro Runde beliebig viele, aber mindestens eine Bombe auf seinen Lieblingsgegner werfen. Nichgeworfene Bomben
verschwinden von allein.
Das Spiel endet nach n Runden.
Der Spieler hat gewonnen, wenn er nur im Gesamten Spiel weniger als 2*n Bomben geworfen hat.Ich will die Wahrscheinlichkeit dafür bestimmen, indem ich einen Brutforcer alle möglichen Spielverläufe durchprobieren lasse.
Laufzeit O(n^PI)
-
Ihr macht ja sogar die sinnlosesten Aufgaben mit
-
War völlig falsch. Ich habe nur O(PI^n) gemacht. Für O(n^PI) oder O(n^3.14) oder O(n^(22/7)) habe ich keine Idee.
