Avatar billede hansent Nybegynder
28. marts 2002 - 11:12 Der er 3 kommentarer og
1 løsning

Big-O

Hej allesammen,
Jeg har et spoergsmaal angaaende big-O.
Jeg skal angive om nedenstaaende algorithmer er
O(n) eller O(n^2). Er der nogen der kan forklare hvordan man kan finde ud af det?
Jeg har en ide om at a og c er O(n^2) og at b er
O(n), men jeg ved det ikke med sikkerhed.
Paa forhaand tak!


a. for (i=0; i<n; i++)
    for (j=o;j<n; j++)
        cout << i<< ' ' << j;

b. for (i=0; i<n; i++)
    for (j=1;j<=2; j++)
        cout << i<< ' ' << j;

c. for (i=0; i<n; i++)
    for (j=n;j>n; j-)
        cout << i<< ' ' << j;


Avatar billede laffe Nybegynder
28. marts 2002 - 11:15 #1
Det er rigtig. a og c er O(n^2)

fordi du har to nestede løkker der kører fra 1 to n.

I b kører den inderste løkke kun til 2, altså en konstant værdi.
Avatar billede laffe Nybegynder
28. marts 2002 - 14:10 #2
Jeg ser lige at koden til c ser lidt mærkelig ud.
Er der ikke en skrive-bøf ?

c. for (i=0; i<n; i++)
    for (j=n;j>n; j-)    <----------------------------j- ??????
        cout << i<< ' ' << j;

Skulle der ikke stå j-- ?
Avatar billede laffe Nybegynder
28. marts 2002 - 14:12 #3
for (j=n;j>n; j--)

vil i så fald aldrig blive kørt, da j aldrig bliver > n, og så er den heller ikke O(n^2), men O(n).
Avatar billede hansent Nybegynder
28. marts 2002 - 17:50 #4
Hej laffe,
Jo det er en skrivefejl mht j-.
Mange tak for dit svar, det var hvad jeg haabede paa.
Avatar billede Ny bruger Nybegynder

Din løsning...

Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.

Loading billede Opret Preview
Kategori
Kurser inden for grundlæggende programmering

Log ind eller opret profil

Hov!

For at kunne deltage på Computerworld Eksperten skal du være logget ind.

Det er heldigvis nemt at oprette en bruger: Det tager to minutter og du kan vælge at bruge enten e-mail, Facebook eller Google som login.

Du kan også logge ind via nedenstående tjenester