|
|
|
|
|
|
|
| | Zitat von SilentAssassin
jetzt setze z = a^2 und du hast nur noch eine quadratische gleichung zu lösen.
| |
Habe ich versucht, funktioniert natürlich auch, aber so richtig gut lässt sich das von Hand leider auch nicht rechnen. 
|
|
|
|
|
|
|
|
|
|
|
Quadratische Ergänzung und gib ihm. Vielleicht hilft es, dass 3,75 auch geschrieben werden kann als 2^2-0,5^2, weil das 4-0,25 ist und damit könnte man die dritte binomische Formel anwenden um (2-0,5)(2+0,5) zu bekommen.
I swear, it's like I'm telling my life story to Statler and Waldorf.
|
|
|
|
|
|
|
|
|
|
|
| | Zitat von ChrisR
Ok, danke Leute, das hat mir auf jedenfall schonmal geholfen. Ich hab jetzt ca. 3 Firmen in der näheren Auswahl und werde mich bei denen dann einfach mal bewerben und sehen, wo ich überhaupt genommen werden. Darunter ist jetzt eine relativ kleine (<100) und zwei mittelständische Firmen (>1000). Falls ich mehr als eine Zusage bekommen sollte, werde ich es wohl vom Vorstellungsgespräch abhängig machen, ist ja auch wichtig ob die Sympathie stimmt ...
Und Hyperdeath kann ich da auch nur zustimmen, Gehalt ist mir am Anfang relativ nebensächlich ... ich will was machen, was mir Spaß macht und dabei möglichst viel lernen!
Mal noch ne andere Frage: Hab jetzt effektiv noch 2 Hochschulsemester und möchte da natürlich noch soviel es geht mitnehmen. Mit welchen Techniken\Bereichen\Programmiersprachen usw. würdet ihr euch auseinandersetzen, wenn ihr nochmal an der Hochschule wärt bzw. was hat euch am meisten gebracht? Egal ob es jetzt für Job oä relevant ist oder nur aus eigenem Interesse!
| |
Noch eine Infoquelle: www.kununu.com/
Ein Arbeitgeberbewertungsportal. Klar, manche Beiträge sind von frustrierten Ex-Mitarbeitern, also nicht alles glauben, was man im Internet liest!
|
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von krischan111 am 07.04.2013 15:58]
|
|
|
|
|
|
|
|
| | Zitat von Wraith of Seth
Quadratische Ergänzung und gib ihm. Vielleicht hilft es, dass 3,75 auch geschrieben werden kann als 2^2-0,5^2, weil das 4-0,25 ist und damit könnte man die dritte binomische Formel anwenden um (2-0,5)(2+0,5) zu bekommen.
| |
Ich hab jetzt -3.75 einfach als -15/4 geschrieben, damit lies sich besser rechnen, aber so richtig schön war das auch nicht. 
Danke euch beiden jedenfalls.
|
|
|
|
|
|
|
|
|
|
|
| | Zitat von Hyperdeath
¤\So eine ähnliches Diskussion hatten wir doch erst vor ein paar Wochen, oder?
| |
Kann sein, ja
Ich sehe den Vorteil den Vorteil rein-funktionaler Programmierung auch nicht so richtig. Daher mag ich Scala ja auch. Erstmal kann man damit relativ sauber funktional programmieren, wenn man es möchte, wenn es sich gerade anbietet. Dann kann man damit aber auch schön prozedural und objektorientiert programmieren, wenn sich das anbietet.
Und um das etwas schöner zu machen bekommt man halt schöne algebraische Datenstrukuren und wird ein bisschen zu unveränderlichen Typen und Referenzen hingeschoben.
Und wenn die JVM dann irgendwann mal die Unterstützung der funktionaleren Konstrukte einbaut wird das ganze auch schnell. Und bis dahin verwendet man es halt halt nur in unkritischen Teilen.
|
|
|
|
|
|
|
|
|
|
Ich hab folgendes Problem :
Zu dem Algo soll ich nun die Laufzeit bestimmen nur hab ich keine Ahnung wie das geht..
Vielleicht hat wer paar Tipps dazu.
|
|
[Dieser Beitrag wurde 1 mal editiert; zum letzten Mal von b4ckspin am 07.04.2013 22:38]
|
|
|
|
|
|
|
|
|
|
Ohne mir das genauer angeguckt zu haben: Rekursionsgleichung aufstellen und Mastertheorem anwenden
|
|
|
|
|
|
|
|
|
|
|
Also ich habe mit dem wissen dass alles was sortiert immer* nlogn ist mal drübergeschaut und würde sagen, dass du höchstens logn rekursive aufrufe von mergesort hast (warum?) und jedes merge n schritte braucht -> bäm
*wahrscheinlich nicht...
|
|
|
|
|
|
|
|
|
|
|
| | Zitat von Ballardbird_Lee
Also ich habe mit dem wissen dass alles was sortiert immer* nlogn ist mal drübergeschaut und würde sagen, dass du höchstens logn rekursive aufrufe von mergesort hast (warum?) und jedes merge n schritte braucht -> bäm
*wahrscheinlich nicht...
| |
* Man kann auf einer Comparison-RAM in höchstens O(n*log n) Zeit sortieren. Für Merge-Sort ist im allgemeinen diese Grenze scharf.
Das hilft ihm aber nicht für diese Aufgabenstellung. Denn es ist ja nicht gezeigt, dass der Code auch wirklich ein Merge-Sort ist. 
|
|
|
|
|
|
|
|
|
|
|
|
naja dann weißt man das eben nach.. sieht doch ganz vernünftig aus
|
|
|
|
|
|
|
|
|
|
|
Mit E(n) meine ich Theta(n).
| |
| Code: |
1 | MergeSort(A, p, r): | n = r - p, T(n) = 2 * T(n/2) + E(1) + T'(n) = 2 * T(n/2) + E(n)
2 | if p < r then | E(1)
3 | q <- (p+r)/2 | E(1)
4 | MergeSort(A, p, q) | T(n/2)
5 | MergeSort(A, q + 1, r) | T(n/2)
6 | Merge(A, p, q, r) | T'(n)
7 |
8 |
9 |
10 |
11 | Merge(A, p, q, r): | n = r - p, T'(n) = "6 * E(1)" + "4 * E(n)" = E(n)
12 | n1 <- q - p + 1 | E(1)
13 | n2 <- r - q | E(1)
14 |
15 | define L, R | E(n)
16 |
17 | for i <- 1 to n1 do | E(n)
18 | L[i] <- A[p + i - 1] | -- E(1)
19 |
20 | for j <- 1 to n2 do | E(n)
21 | R[j] <- A[q + j] | -- E(1)
22 |
23 | L[n1 + 1] <- infty | E(1)
24 | R[n2 + 1] <- infty | E(1)
25 | i <- 1 | E(1)
26 | j <- 1 | E(1)
27 |
28 | for k <- p to r do | E(n)
29 | if L[i] <= R[j] then | -- E(1)
30 | A[k] <- L[i] | -- E(1)
31 | i <- i + 1 | -- E(1)
32 | else
33 | A[k] <- R[j] | -- E(1)
34 | j <- j + 1 | -- E(1)
|
|
Das ist etwas informell, aber ich hoffe es zeigt dir die Idee.
Man kann die Laufzeit eines Algorithmus ermitteln, indem man die Laufzeit der einzelnen Aufrufe analysiert und danach summiert. Beim Summieren helfen die Landausymbole ungemein weil sie nervige Konstanten einfach verschlucken - deswegen benutzt man die so gern.
Unser Ziel ist es die Laufzeit von "MergeSort" in Abhängigkeit von n zu ermitteln, die Funktion nennen wir T(n). n ist die Anzahl der Elemente die sortiert werden sollen deswegen gilt "n = r - p". Das postuliere ich hier einfach mal, man sollte das vllt etwas begründen.
Danach schauen wir den Code von MergeSort zeilenweise an. Vergleiche und Zuweisungen brauchen konstante Zeit. Danach erkennen wir dass in den beiden rekursiven Aufrufen jeweils nurnoch (etwa) die Hälfte der Elemente sortiert wird, also T(n/2) Zeit gebraucht wird. Danach wird noch das magische Merge aufgerufen, das, behaupten wir einfach mal, T'(n) Zeit braucht. Es ergibt sich also eine Gesamtlaufzeit T(n) = 2 * T(n/2) + E(1) + T'(n). Beachte wie die E(1) "verschmelzen".
Für diese Art von Rekursionsgleichung bietet sich das Master-Theorem an, das wir hier ja schon ein paar mal hatten. Dafür müssen wir aber erstmal noch rausfinden was T'(n) ist, zumindest in welcher (Landau-)Klasse von Funktionen es liegt.
Also machen wir für Merge das selbe Spielchen wieder. Auch hier ist "n = r - p" und wir stellen voller Freude fest, dass keine rekursiven Aufrufe existieren. Dafür aber Schleifen, dazu kommen wir aber gleich.
Die Laufzeit von Merge ist die Laufzeit der "Blöcke" summiert. Zeilen 12, 13, 23, 24, 25, 26 sind alles Zuweisungen und brauchen E(1) Zeit. Ich gehe hier mal pessimistisch davon aus dass Zeile 15 E(n) Zeit braucht, weils im Grunde egal ist.
Anhand von Zeilen 17 und 18 will ich kurz den Umgang mit Schleifen erklären: In Zeile 17 steht, dass der Schleifenkörper E(n) mal ausgeführt wird. Man könnte genauer sagen dass das wsl irgendwas um n/2 sein wird, aber für die asymptotische Betrachtung ist der Vorfaktor egal, deswegen passt E(n) schon. Im Körper findet sich nur eine Zuweisung, die dauert E(1). Die ganze Schleife dauert dann E(1) * E(n) = E(n) Zeiteinheiten, die Summe der Zeilen des Körpers multipliziert mit der Anzahl der Aufrufe, was man intuitiv erwarten würde. Das ganze ist natürlich rekursiv für Schleifen in Schleifen usw. Das Spiel macht man auch für die ganzen anderen Schleifen.
Dann kommt raus, dass T'(n) = E(1) + E(n) = E(n).
Also ist T(n) = 2 * T(n/2) + E(n).
Damit ist T(n) sowohl von oben als auch von unten durch n * log n beschränkt.
e/ Der letzte Schritt ist Master Theorem und auf der Wikiseite sogar im Beispiel beschrieben.
|
|
[Dieser Beitrag wurde 2 mal editiert; zum letzten Mal von B0rG* am 08.04.2013 3:46]
|
|
|
|
|
|
| Thema: pOT-lnformatiker, Mathematiker, Physiker XII ( Jetzt mit Primzahlen > 1024 ) |
|
