Komplexität von Schleifen < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:16 Mo 07.08.2006 | | Autor: | peterw |
Hallo,
ich habe unten stehendes Java Programm und würde gern die Komplexität abschätzen. Genauer gesagt die Komplexität der while-Schleife.
Ist die List list mit N Elementen gefüllt, so ist der Aufwand [mm] \summe_{i=1}^{N} [/mm] 1 . Welchem O() entspricht dies? [mm] O(N^{2})? [/mm] Falls ja, wieso?
Mir wurde gesagt, dass die innere Schleife eine Komplexität von [mm] N^{2}/2 [/mm] haben soll. Kann mir das jemand erklären? Und warum ist das bei mir nicht so?
Bei N=16 ist die Ausgabe 136 = [mm] N^{2}/2 [/mm] + 8
Bei N=32 ist die Ausgabe 528 = [mm] N^{2}/2 [/mm] + 16
Danke.
Grüße,
Peter
PS: Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
public class complexity {
public static void main(String[] args) {
Random random = new Random(1);
List<String> list = new ArrayList<String>();
for (int i=0; i<4;i++) {
list.add(String.valueOf(i));
}
int count =0;
while (!list.isEmpty()) {
for (int i=0;i<list.size();i++) {
count++;
System.out.print(".");
}
list.remove(random.nextInt(list.size()));
}
[mm] System.out.println("\ncount="+count);
[/mm]
}
}
|
|
| |
|
Hallo und guten Morgen,
die for-Schleife innerhalb der while-Schleife benoetigt O(Größe der Liste) viele Schritte, und bei jedem Durchlauf der While-Schleife
wird genau ein Listenelement entfernt, so dass die while-Schleife also insgesamt
[mm] O(\sum_{i=1}^{S}i)=O(S^2) [/mm] Schritte braucht, wobei S die Groesse (=Anzahl Einträge) der Liste vor Beginn der While-Schleife sei.
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 08:42 Di 08.08.2006 | | Autor: | peterw |
Guten Morgen,
vielen Dank für die Antwort. Ich hätte noch zwei Nachfragen.
- Wie kommst Du auf die Gleichheit von $ [mm] O(\sum_{i=1}^{S}i)=O(S^2) [/mm] $ ? Gibt es irgendwo eine Übersicht über solche Umformungen oder muss man das einfach sehen?
- Was wäre der Aufwand, wenn man das gleiche While-For-Konstrukt innerhalb des ersten hätte. Also die Elemente der Liste wieder Listen sind, die durchlaufen werden.
While (Liste L nicht leer)
For (jedes Element E der Liste L)
While (Liste E nicht leer)
For (jedes Element der Liste E)
Ist das dann [mm] O(N^2) [/mm] * [mm] O(M^2) [/mm] = [mm] O(N^2 [/mm] * [mm] M^2) [/mm] mit M=max. Größe der Listen in L.
Nocheinmal danke.
Grüße,
Peter
|
|
|
| |
|
Moin Peter,
es ist doch [mm] \sum_{i=1}^{S}i=\frac{S\cdot (S+1)}{2}\leq 2\cdot S^2.
[/mm]
Und zur zweiten Frage: Das wäre dann sowas wie
[mm] \sum_{i=1}^{S}i\:\: +\:\: \sum_{i=1}^S \: (Size(Liste\:\: L_i))^2
[/mm]
(denn die Listen werden beim ersten Durchlauf komplett geleert.
Woher kommt man auf solche Fragen, und warum gibt man sich das Kürzel peterw ?
Gruss,
Mathias
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:51 Di 08.08.2006 | | Autor: | peterw |
Hi Mathias,
Danke für die schnelle Antwort.
> Woher kommt man auf solche Fragen, und warum gibt man sich das Kürzel peterw ?
Um zuserst auf Deine Fragen einzugehen:
- Wie kommt man auf mathiash? (Vorname+Nachname?)
- Ich will gerne wissen, welchen Aufwand ein von mir entwickelter Algorithmus hat. Kein toller Algorithmus, aber ich hatte erst gedacht, dass der Aufwand wesendlich schlechter als [mm] O(N^2) [/mm] ist. Nachdem das nicht so ist, möchte ich es einfach genauer verstehen.
> (denn die Listen werden beim ersten Durchlauf komplett geleert)
Da habe ich was falsch gemacht. Die Listen [mm] L_i [/mm] werden nicht geleert. Von ihnen wird vorher eine Kopie erstellt mit der dann gearbeitet wird.
Also:
While (Liste L nicht leer)
For (jedes Element [mm] L_i [/mm] aus L)
E = [mm] Kopie(L_i)
[/mm]
While (Liste E nicht leer)
For (jedes Element der Liste E)
tueEtwas
removeRandom(E)
removeRandom(L)
Ist in diesem Fall meine Vermutung mit [mm] O(n^2*m^2) [/mm] richitig?
|
|
|
| |
|
Moin Peter,
ich würd sagen: Ja.
Gruss,
Mathias
|
|
|
|
