Her kan du stille spørsmål vedrørende problemer og oppgaver i matematikk på høyskolenivå. Alle som har kunnskapen er velkommen med et svar. Men, ikke forvent at admin i matematikk.net er spesielt aktive her.
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
There are only 10 kinds of people. Those who understand binary and those who don't.
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 [tex]i+2i+3i+ \ldots +i^2= \frac {i^2(i+1)} 2[/tex]. Siden i løper fra og med 1 til og med n betyr dette at du må summere [tex]\frac {i^2(i+1)} 2[/tex] 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.
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?
There are only 10 kinds of people. Those who understand binary and those who don't.
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 [tex]1 + 4 + 9 + \ldots + n^2 = O(n^3)[/tex]. 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 [tex] \frac 1 6 n(n+1)(2n+1)[/tex].) Du sier ikke at summen er 'lik' eller 'tilnærmet lik' [tex]n^3[/tex] eller noe, men mer at tiden programmet krever som en funksjon av [tex]n[/tex] vil vokse omtrent som et eller annet tredjegradspolynom for tilstrekkelig store [tex]n[/tex].
