Warning! This is the 2012 course's website! You probably want the current course website.

Inlämningsuppgift 1: Komplexitet (lösningsförslag)

Uppgifter

1. Fyll i tabellen nedan. För varje funktion f(n) och tid t skall ni bestämma det största storleken n som kan lösas under tiden t, där arbetet tar f(n) mikrosekunder.

   För den sista kolumnen ska ni använda summan av antalet år ni har levat totalt. Här har jag räknat på den sammanlagda levnadstiden 42 år = 42·12 månader. Dessutom har jag antagit att en månad är 30 dagar = 30·24 timmar. För att lösa uppgiften krävs att man kommer på vad inversen g(t) är till funktionen f(n), dvs. hitta g så att g(f(n)) = n.

   Inverserna till n! och n log₂ n är inte direkt beräkningsbara (men går att göra i t.ex. Mathematica eller Matlab). För fakulteten är det enklaste att helt enkelt testa sig fram:

         fac = 1
         for n in 1 .. 20:
             fac = fac * n
             print n, fac
       

   Svårast är att lösa ut n log₂ n. Med t.ex. Mathematica eller Matlab kan man använda sig av Lamberts W-funktion (se exempel 4). Men enklast är att låta datorn pröva sig fram genom intervallhalvering, ungefär såhär:

         nmin = 1
         nmax = t
         while nmax - nmin > 0.5:
             nmid = (nmin + nmax) / 2
             if nmid * log2(nmid) < t:
                 nmin = nmid
             else:
                 nmax = nmid
       

   (Självklart kan man använda intervallhalvering för att lösa alla n-värden i tabellen).

   f(n)	n ≤ g(t)	1 sekund ts = 106 μs	1 timme th = (60 · 60) · (106) μs = 3,6 · 109 μs	1 månad tm ≈ (30 · 24) · (3,6 · 109) μs = 2,6 · 1012 μs	sammanlagd levnadstid te ≈ (42 · 12) · (2,6 · 1012) μs = 1,3 · 1015 μs
   log2 n	n = 2log2 n ≤ 2t≈ 100,3·t	n ≤ 10(3,0·105)	n ≤ 10(1,1·109)	n ≤ 10(7,8·1011)	n ≤ 10(3,9·1015)
   √n	n = (√n )2 ≤ t2	n ≤ 1012	n ≤ 1,3 · 1019	n ≤ 6,8 · 1024	n ≤ 1,7 · 1030
   n	n ≤ t	n ≤ 106	n ≤ 3,6 · 109	n ≤ 2,6 · 1012	n ≤ 1,3 · 1015
   n log2 n	n kan lösas med intervallhalvering	n ≤ 62 746	n ≤ 1,3 · 108	n ≤ 7,2 · 1010	n ≤ 2,9 · 1013
   n2	n = √n2  ≤ √t	n ≤ 1000	n ≤ 60 000	n ≤ 1 612 451	n ≤ 36 055 512
   n3	n = 3√n3  ≤ 3√t	n ≤ 100	n ≤ 1532	n ≤ 13 750	n ≤ 109 139
   2n	n = log2 2n ≤ log2 t	n ≤ 19	n ≤ 31	n ≤ 41	n ≤ 50
   n!	Här kan man pröva sig fram helt själv	n ≤ 9	n ≤ 12	n ≤ 15	n ≤ 17

2. Vilken är komplexiteten för följande funktioner? Beskriv med en matematisk funktion hur antalet additionsoperationer beror på n, (vilket är detsamma som funktionsresultatet). Ange sedan ordo-funktionen.

   OBS! De tre sista funktionerna (Ex8, Ex9 och Ex10) är svåra att beräkna exakt! Så där räcker det med enbart ordo-funktionen som svar.

   Här är en sammanfattning av resultaten:

   Ex	f(n)	O(n)	Kommentar
   1	n – 1	O(n)	En enda loop ger linjär komplexitet
   2	(n – 1)2	O(n2)	Två nästade loopar ger kvadratisk komplexitet
   3	2n	O(n)	Två linjära loopar efter varandra blir fortfarande linjär
   4	(n – 1) · (n2 – 1)	O(n3)	Eftersom den andra loopen går igenom kvadratiskt många värden, så får vi n · n2 = kubisk komplexitet
   5	n · (n – 1) / 2	O(n2)	Två nästade loopar ger kvadratisk komplexitet; den inre loopen går i genomsnitt igenom ungefär n/2 gånger
   6	n · (n – 1) · (n – 2) / 6	O(n3)	Tre nästade loopar ger kubisk komplexitet; de inre looparna går i genomsnitt igenom ungefär n/2 resp. n/3 gånger
   7	n	O(n)	Ex7(n) anropar Ex7(n–1) endast en gång, och då får vi linjär komplexitet
   8	⎣log2 n⎦	O(log n)	n halveras vid varje rekursivt anrop, och det är typiskt för logaritmiska algoritmer
   9	gränsvärdet är n! · e – 1	O(n!)	Ex9(n) = n · (1 + Ex9(n–1)), vilket är större än n · Ex9(n–1) = n! Gränsvärdet kan man få genom att pröva sig fram, eller genom att översätta till Gamma-funktionen och vara duktig på matematik.
   10	—	≈ O(n½·log n + 1)	Ex10(n) = n · (1 + Ex10(⎣n/2⎦)) vilket är mycket mindre än Ex9, men inte självklart var någonstans det hamnar; se nedan för en matematisk diskussion

   Här är en förklaring av sista uppgiften:

   • Ex₁₀(n) = n · (1 + Ex₁₀(⎣n/2⎦)).
   • Förenkling ger att Ex₁₀(n) > n · Ex₁₀(n/2), och alltså att Ex₁₀(n) > f(n), där f(n) = n · f(n/2).
   • f(n) kan vi beräkna såhär: f(n) = n · n/2 · n/4 · n/8 ··· = 2^log n · 2^{log n – 1} ··· 2⁰ = 2^{(log n) · (log n + 1)/2} = (2^log n)^{(log n + 1)/2} = n^{(log n + 1)/2}.
   • En annan förenkling get att Ex₁₀(n) < n · (Ex₁₀(n/2) + Ex₁₀(n/2)) = 2n · Ex₁₀(n/2), och alltså att Ex₁₀(n) < g(n), där g(n) = 2n · g(n/2).
   • Men g(n) = 2n · 2n/2 · 2n/4 ··· = 2·2···2 · f(n) = 2^1+log n · f(n) = 2n · f(n) = 2n · n^{(log n + 1)/2} = 2 · n^{(log n + 3)/2}.
   • Alltså ligger Ex₁₀(n) mellan O(n^{(log n + 1)/2}) och O(n^{(log n + 3)/2}).
   • Komplexiteten för Ex₁₀ blir alltså ungefär i runda slängar O(n^{½·log n + 1}).
   • Eftersom exponenten växer kontinuerligt så växer Ex₁₀(n) snabbare än O(n^a) för alla a.
   • Men är då Ex₁₀(n) exponentiell? Nja, om vi testar mot vilken exponentiell funktion som helst, så går exponentialfunktionen om till slut. Alltså är n^log n, n^½·log n, n^{½·log n + 1} och deras kompisar en helt egen funktionsklass, vars komplexitet ligger mellan polynomiella och exponentiella funktioner.

   Som synes blev det lite komplicerat… En till synes enkel funktion kan alltså vara väldigt svår att analysera, speciellt om den är rekursiv. Som tur är kommer vi inte att stöta på sådana algoritmer i denhär kursen.

   Här är slutligen funktionerna som de gavs i uppgiften:

   public int Ex1(int n) {
     int sum = 0;
     for (int i = 1; i < n; i++)
       sum += 1;
     return sum;
   }
   
   public int Ex2(int n) {
     int sum = 0;
     for (int i = 1; i < n; i++)
       for (int j = 1; j < n; j++)
          sum += 1;
     return sum;
   }
   
   public int Ex3(int n) {
     int sum = 0;
     for (int i = 0; i < n; i++) 
       sum += 1; 
     for (int j = 0; j < n; j++) 
       sum += 1; 
     return sum;
   }
   
   public int Ex4(int n) {
     int sum = 0;
     for (int i = 1; i < n; i++)
       for (int j = 1; j < n*n; j++)
          sum += 1;
     return sum;
   }
   
   public int Ex5(int n) {
     int sum = 0;
     for (int i = 0; i < n; i++) 
       for (int j = 0; j < i; j++) 
         sum += 1; 
     return sum;
   }
   
   public int Ex6(int n) {
     int sum = 0;
     for (int i = 0; i < n; i++) 
       for (int j = i+1; j < n; j++) 
         for (int k = j+1; k < n; k++) 
           sum += 1; 
     return sum;
   }
   
   public int Ex7(int n) {
     if (n > 0)
       return 1 + Ex7(n-1);
     else 
       return 0;
   }
   
   public int Ex8(int n) {
     if (n > 1)
       return 1 + Ex8(n/2);
     else 
       return 0;
   }
   
   public int Ex9(int n) {
     int sum = 0;
     for (int i = 0; i < n; i++) {
       sum += 1 + Ex9(n-1);
     return sum;
   }
   
   public int Ex10(int n) {
     int sum = 0;
     for (int i = 0; i < n; i++) {
       sum += 1 + Ex10(n/2);
     return sum;
   }