Allg. Laufzeitformel < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Aufgabe | Geben Sie eine allgemeine Formel für die Laufzeit an.
for(int i=1;i<=n;i++)
{
for(int j=1;j<i;j+=2)
{
var++;
}
} |
Hi, vllt. könnt ihr mir ja gerade helfen.
Hier meine Frage wie bekomme ich das j+=2 auf der in inneren For Schleifen in mein Summenzeichen.
[mm] \summe_{i=1}^{n}( \summe_{j=1}^{i} [/mm] ?)
Danke schonmal und für Tipps wie es dann weiter geht bin ich auch noch offen^^
MFG
|
|
| |
|
Hallo carlito83,
> Geben Sie eine allgemeine Formel für die Laufzeit an.
>
> for(int i=1;i<=n;i++)
> {
> for(int j=1;j<i;j+=2)
> {
> var++;
> }
> }
>
> wie bekomme ich das j+=2 auf der in
> inneren For Schleifen in mein Summenzeichen.
>
> [mm]\summe_{i=1}^{n}( \summe_{j=1}^{i}[/mm] ?)
Also die innere Summe sollte bis [mm]i-1[/mm] laufen und nicht bis [mm]i[/mm]. Die innere Schleife zählt hier im Schleifenkopf alle ungeraden Zahlen zwischen [mm]1[/mm] und [mm]i-1[/mm] auf. Das Problem ist, daß [mm]i-1[/mm] hier gerade und im nächsten Schritt wieder ungerade sein kann. Aber die Gauß-Klammer (nach oben runden) sollte hier helfen. Damit wird die innere Schleife [mm]\left\lceil\tfrac{i-1}{2}\right\rceil[/mm] mal aufgerufen, weil ungefähr die Hälfte der natürlichen Zahlen zwischen [mm]1[/mm] und [mm]i-1[/mm] (un)gerade Zahlen sind.
Um dann weiter mit diesem Term die äußere Summe aufzulösen, mußt du - denke ich mal - eine Fallunterscheidung: "[mm]i[/mm] (un)gerade" machen, um dann die entgültige exakte Laufzeit zu bekommen, oder aber du nimmst später die [mm]\mathcal{O}\texttt{-Notation}[/mm] und gehst deswegen vom schlechteren Fall aus, daß nach oben gerundet wird.
Viele Grüße
Karl
|
|
|
|
