Informatikk: Big-O-analyse

[luringen]

Ikke direkte matematikk-relatert, men håper noen kan svare her på forumet.

Er en oppgave hvor man skal gjøre en "Big-O"-analyse av en nested for-loop.
Altså finne en generell formell for hvor mange ganger 'sum++;' vil kjøre.

Slik ser den ut:

Code: Select all

for (int i = 1; i <= n; i++)
    for (int j=1; j <= i*i; j++)
        if (j % i == 0) 
            for (int k=0 ; k < j ; k++)
                sum++;

Det blir litt vanskelig å tenke seg frem til resultatet med så mange parametere som spiller i hverandre. Finnes det en fremgangsmåte, eller et sett å tenke på som gjør slik oppgaver lettere?


mvh luringen

[Karl_Erik]

Antar at j % i == 0 vil si at j mod i skal være null, dvs at i skal dele j. Da j kan være høyst i^2 ser vi at j=i, j=2i, ..., j=(i-1)i, j=i^2 er de eneste verdiene av j slik at j % i == 0. Altså vil if-utsagnet kun være sant i ganger. For hver av disse gangene kjøres sum++ j ganger, og da j=i, 2i osv kjøres den totalt $i+2i+3i+\dots +i^2=\frac{i^2(i+1)}{2}$. Siden i løper fra og med 1 til og med n betyr dette at du må summere $\frac{i^2(i+1)}{2}$ fra i=1 til i=n, noe som blir litt kronglete men fullt gjennomførbart. Er du dog 'bare' interessert i en Big O-analyse ser vi at summen vil bli et fjerdegradspolynom i n.

[luringen]

Takk skal du ha for svar. Men et spørsmål. Sånn som for eksempel den andre for-løkka som vil gå først 1 gang så 4, 9, 16, ... til n*n ganger. Pleier man da med O-notasjon å generalisere det til n*n*n? Det blir vel et relativt stort overslag?

[Karl_Erik]

Joda, du kan godt kalle det det, men du må huske på at poenget med kompleksitetsanalyse ikke er å finne den eksakte verdien av funksjonen, men bare hvordan den vokser i det lange løp. I spørsmålet ditt spør du vel egentlig om det er 'riktig' å skrive $1+4+9+\dots +n^2=O(n^3)$. Om du tenker litt over definisjonen av O-notasjon er det du egentlig spør om da er om summen av kvadrattallene oppfører seg som et tredjegradspolynom, noe det tross alt gjør. (Den er faktisk lik $\frac{1}{6}n(n+1)(2n+1)$.) Du sier ikke at summen er 'lik' eller 'tilnærmet lik' $n^3$ eller noe, men mer at tiden programmet krever som en funksjon av $n$ vil vokse omtrent som et eller annet tredjegradspolynom for tilstrekkelig store $n$.