Effiziente Algorithmen

Hallo,

wie kann ich folgende Logarithmusfunktion
t(n)=n*log2(n)
nach n auflösen


Gruß Holger

 

garnicht

kannst du nur nummerisch "zurückrechnen"

 

> garnicht
Stimmt nicht.


Für x > 0 ist die Fktn. x * log(x) injektiv, nach Verschiebung x -> x+1 surjektiv auf R+, ergo bijektiv und damit umkehrbar. Es existiert damit eine Umkehrfktn. von x * log(x).


Zweitens ist x * log(x) um die 1 nach Taylor entwickelbar...

Nehme die Entwicklung von log(x) nach 1
und erhalte per (x - 1 + 1) * log(x)
= (x -1) Tlog(x-1) + Tlog(x-1)


Bleibt der übliche KoeffizientenVergleich für die Umkehrung von Potenzreihen.

Unterm Strich: Eine "einfache Formel"? - Kaum. Aber zumindest eine Taylor-Entwicklung.

 

ich will da jetzt nicht den grossen mathematiker raushängen lassen (ist zu lange her bei mir )

aabbeerr: egal wie und wohin du x*log(x, 2) auch verschiebst, die umkehrfunktion (so sie existiert) ist keine abbildung, weil im y-werte-bereich zwischen dem minimum von x*log(x, 2) (bei x=e^(-1) und y = -e^(-1)/ln(2)) und 0 für jedes y zwei x-werte existieren. ergo kann keine geschlossene lösung existieren. da hilft auch keine reihenentwicklung.

also für die einzelnen äste: möglich
für die komplette funktion: sicher nicht.

btw: so arg genau sind die taylorfolgen übrigens auch nicht:
http://img101.exs.cx/img101/8077/xlogx.jpg

 

f(x) = x* log(x) hat eine Nullstelle bei x=1 und eine (behebbare) bei x=0 (mit f(0)=0 OT l'Hospital) und vermöge Konvexität ein Min. dazwischen. Für die beiden Äste [0; Min] und [Min.; unendl] ist f injektiv, insbesondere, wenn ich den rechten Ast einschränke auf [1; unendl.].

Die von mir genannte Verschiebung (x-> x+1) bedeutet, dass die Funktion (konkret sieht sie so aus...) (x + 1) * log(x+1) auf [0; unendl] injektiv (bleibt) und auf R+ surjektiv ist.

Soviel zum Thema "Umkehrfunktion ist keine Abb.".


Erinnerung: Was haben wir bei x^2 denn anders gemacht? - Wir haben den *bösen* Ast x < 0 weggelassen, festgestellt, dass x*x auf x > 0 bijektiv ist (Umkehrfktn. exist.) und diese dann frech "Wurzel" genannt...


Im Topic.Fall wäre ich also formal fertig durch Erfinden eines Namens für die Umkehrfktn. von (x+1)* log(x+1), so wie es mit SQRT bzw. "Wurzel" passiert ist.

Man hätte es auch einfacher nehmen können und den uninteressanten [0; 1]-Teil ignorieren können, denn n -> n*log(n) suggeriert n=natürlich, bei indef. n=0...


Was bleibt nach Existenz-/ Eindeutigkeitsfragen? - How ugly! "Wie sieht die Umkehrfunktion aus?" Hier bietet Taylor / Potenzreihen IMO hinreichende Anschauung.

Thema "Taylor": Eine Taylor-Reihe hat einen Index i=0..unendl. und falls der Index endl. ist (je nach Angebot des Satzes), gibt es zB. einen sog. IntegralKern. Insbesondere kann ich nicht eine Restreihe *vergessen* und sagen, "Taylor approximiert schlecht". Für die Analysis ist Taylor exakt! Aus der Numerik ist (dann!) allgemein bekannt, wie schlecht Polynome überhaupt (global) interpolieren. Da nimmt man Splines, geeignete Stützstellen etc., spricht aber selten über die Existenz einer Umkehrfunktion...


> ...ist zu lange her bei mir
Ist bei mir auch *etwas* her. Lange? - Hmm. "Zu lange"? - NIE!

___________________________

eckige Klammern [] bitte nicht als abgeschl. interpret. ...
Das "Min." ist irgendwas aus [0; 1] je nach Log.Modul

 

Danke für die Antworten.

Folgende Aufgabe ist zu lösen.

Angenommen man findet einen Algorithmus, der bei der Eingabegröße n mit t(n)=n*LOG(n,2) vergleichen auskommt.
Welche Eingabegröße n kann man nun in 10 Sekunden bearbeiten?
Die CPU kann pro Sekunde 10 Millionen Vergleiche ausführen.

Vielen dank im voraus

 

habe mittlerweile verstanden was du gemeint hast.
-> insofern hast du recht

ändert aber nichts am problem von DeadCunt52: geschlossen lässt sich (mit meinem wissen) keine lösung angeben

 

Du meinst, er hat das "o" bei "Count" tatsächlich bewusst weggelassen? - Vermutung: Nevok / Ossilotta wälzen (immer noch) das Wörterbuch und das böze Wort kommt nicht vor.

Naiv, wie ich nun mal bin, dachte ich, er *zählt* die [1] Programmschritte in (existenten) Sortierverfahren ´, wie zB. Quicksort (C.A.R. Hoare), Shaker- und Bubble- und sucht nun die DatensatzAnzahl n für einen Prog.aufwand S= C*n*log(n); C=const.[masch.abh.]

Deshalb werde ich ihm die richtige Lösung auch nicht verraten, da hast Du völlig recht. - Böze Nicks bekommen böze Antworten. *harhar* Dass allerdings aus Bergkamen(?) keine Unterstützung kam, führe ich auf eine nachtschlafene Zeit hin... Wölfchen macht Schönheitsschlaf.


Es trifft aber völlig den Fall der üblichen, falschen Problembeschreibung. - Es geht NICHT um die Umkehrung einer Funktion, sondern um [1], eine Hausaufgabe?!

Für den Ansatz C*n*log(n) ~ S transformiert man *newton-gerecht* in C*n*log(n) - S = 0... und damit endet mein Support.


Für diese Antwort erwarte ich Strafen von 4 Seiten... *g*

 

> problem von DeadCunt52

Den juckt eher Quicksort und das formale Problem das n einer Folge a(n) herzukriegen. - Siehe "Ansatz per Newton". Unsereins *schachtelt* wohl eher?

Nix für ungut. - Ein IMO ergiebiges Gespräch über verflossene Liebschaften.

_________________

Edit: Ein geringfügiges (aber notwendiges) Smilie ergänzt

 

Der Nick wurde geändert. *siehste* (Schaden abgewendet).

Cunt -> Trust ... Die Veränderung verschliesst sich mir. *egal* Es IST passiert. Alles andere bleibt mir auch unklar. - Bliebe noch der Nachweis, dass Quick-Sort (@CAR.Hoare) die genannte, exakte proport.Effizienz hat und was das C (=const.per Machine) bedeutet, liefert Google.


Abgesang...
...
..
.
Refrain... "Wer schmiert, besser erst mit Newton iteriert" *dideldumdei* [frei übersetzt nach H.Pythagoräus Psalm #2]