Informatiker Board | Theoretische Informatik | Komplexizität

Informatiker Board » Themengebiete » Theoretische Informatik » Komplexizität - O Notation

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Komplexizität - O Notation

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

xole_X
Grünschnabel

Dabei seit: 23.10.2007
Beiträge: 9

Komplexizität - O Notation

Zitatantwort auf diesen Beitrag erstellen

Hallo
ich muss von einem code die komplexizität bestimmen, was ich auch bereits getan hab...mein Problem liegt eher darin, wie man das zeug sauber aufschreibt. den code darf ich hier leider net posten, aber hier einfach nur ein anderes beispiel (konsumiert 2 gleichgroße nxn matrizen und addiert diese)

1. public sum(int a[][],int b[][]){
2. int reihe = a.length;
3. int zeile = a[0].length;
4. int[][] summatrix = new int[reihe][zeile];
5.
6. for(int i = 0; i<reihe; i++)
7. for(int j = 0; j<zeile; j++)
8. summatrix[i][j] = a[i][j]+b[i][j]
9.
10. return summatrix;
11. }

ich hätte jetzt einfach bei meinem code gesagt:
zeile2: c1
zeile3: c2
zeile4: c3
zeile6: n
zeile7: n
zeile8: c4
zeile10: c5

T(n) = c1+c2+c3+n*(n+c4)+c5 € O(n²)

wie schreib ich das aber alles sauber auf? schreibt man da überhaupt für Konstante Aufrufe c hin oder schreib ich da ne 1 oder T(c1) oder T(1)...

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von xole_X: 22.04.2008 21:23.

22.04.2008 20:05

Nehmen Sie xole_X in Ihre Freundesliste auf

ed209
Routinier

Dabei seit: 07.09.2006
Beiträge: 324

Wie genau es sein muß hängt vermutlich von Eurem Prof ab, aber ich würde die Konstanten c1, c2, c3 und c5 zu einer zusammenfassen, die Klammer ausmultiplizieren und dann über die Definition von O gehen.

Gruß,
ED

23.04.2008 08:40

Nehmen Sie ed209 in Ihre Freundesliste auf

Tobias
Routinier

Dabei seit: 18.09.2006
Beiträge: 324

Ich weiß nicht, ob ihr es so umständlich gelernt habt, aber im Allgemeinen gibt man konstanten Operationen den Kostenfaktor "1" bzw. lässt alle in der Eingabegröße konstanten Operationen sofort zu O(1) kollabieren. Man kann ja zeigen, dass es im O-Kalkül keinen Unterschied macht, denn wählte einfach

$[latex]c := \max_i c_i[/latex]$

dann erhälst du

$[latex]T(n) = c_1+c_2+c_3+n(n+c_4)+c_5 \leq 4c + n(n+c) = \mathcal{O}(1) + n(n + \mathcal{O}(1)) = \mathcal{O}(n^2) [/latex]$

23.04.2008 12:02

Nehmen Sie Tobias in Ihre Freundesliste auf

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Komplexizität - O Notation