Effiziente Algorithmen

Dieses Thema im Forum "Smalltalk" wurde erstellt von Trust344!, 18. Dezember 2004.

Status des Themas:
Es sind keine weiteren Antworten möglich.
  1. Trust344!

    Trust344! Guest

    Hallo,

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


    Gruß Holger :bet:
     
  2. Michi0815

    Michi0815 Guest

    Registriert seit:
    7. Januar 2004
    Beiträge:
    3.429
    garnicht :D

    kannst du nur nummerisch "zurückrechnen"
     
  3. MCSE-MCT

    MCSE-MCT Halbes Megabyte

    Registriert seit:
    5. Juli 2004
    Beiträge:
    876
    > 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.
     
  4. Michi0815

    Michi0815 Guest

    Registriert seit:
    7. Januar 2004
    Beiträge:
    3.429
    ich will da jetzt nicht den grossen mathematiker raushängen lassen (ist zu lange her bei mir :D )

    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
     
  5. MCSE-MCT

    MCSE-MCT Halbes Megabyte

    Registriert seit:
    5. Juli 2004
    Beiträge:
    876
    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
     
  6. Trust344!

    Trust344! Guest

    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 :bet:
     
  7. Michi0815

    Michi0815 Guest

    Registriert seit:
    7. Januar 2004
    Beiträge:
    3.429
    habe mittlerweile verstanden was du gemeint hast. :D
    -> insofern hast du recht

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

    MCSE-MCT Halbes Megabyte

    Registriert seit:
    5. Juli 2004
    Beiträge:
    876
    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. :D *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*
     
  9. MCSE-MCT

    MCSE-MCT Halbes Megabyte

    Registriert seit:
    5. Juli 2004
    Beiträge:
    876
    > 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? :D

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

    _________________

    Edit: Ein geringfügiges (aber notwendiges) Smilie ergänzt ;)
     
  10. MCSE-MCT

    MCSE-MCT Halbes Megabyte

    Registriert seit:
    5. Juli 2004
    Beiträge:
    876
    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]
     
Status des Themas:
Es sind keine weiteren Antworten möglich.

Diese Seite empfehlen