Till KTH:s startsida Till KTH:s startsida

Övning 2

Komplexitet

  1. KÖRTIDER

    En viss algoritm tar 0.5 ms när antal indata är 100. Hur lång kommer körtiden att bli när antal indata är 500 om man vet att körtiden är:
    • linjär
    • O(NlogN)
    • kvadratisk
    • kubisk


    Linjär \(k*n\)
    N = 500 k * 500 = x ------------- N = 100 k * 100 = 1/2 5 x = - = 2.5 ms (5x längre) 2 O(NlogN) k * NlogN N = 500 k * 500 * log(500) = x ------------------------ N = 100 k * 100 * log(100) = 1/2 5 * log(500) x = ------------ = 3.37 ms (6.74x längre) 2 * log(100) kvadratisk k * N * N N = 500 k * 500 * 500 = x ------------------- N = 100 k * 100 * 100 = 1/2 5 * 5 x = ----- = 12.5 ms (25x längre) 2 kubisk k * N * N * N N = 500 k * 500 * 500 * 500 = x ------------------------- N = 100 k * 100 * 100 * 100 = 1/2 5 * 5 * 5 x = --------- = 62.5 ms (125x längre) 2

  2. Tidstentan 2014-01-08, uppgift 4 (betyg E + C)
    • Betyg E
      Antalet binära strängar av längd n är 2n. Antalet alfanumeriska (ca 32 olika tecken) strängar av längd m är 32m.

      Vad blir uttrycken ovan om n=10 och m=3?

      Hur mycket större än m måste n vara för att det första uttrycket ska bli större än det andra?

    • Betyg C
      Linda berättar för Alexander att hon bytt till ett lösenord med 45 binära siffror. ''Men herregud!'', säger Alexander, ''Det blir ju alldeles för lätt att knäcka. Själv har jag 9 alfanumeriska tecken i mitt.''

      Vems lösenord är svårast att knäcka med totalsökning?

      Ungefär hur många sekunder tar knäckningen om datorn prövar en miljard lösenord i sekunden?

      Visa dina beräkningar!


    Binära sökträd

  3. TRÄDBYGGEN

    • Hur ser det binärträd ut som skapas om man puttar in talen 4 2 1 6 3 7 5 i denna ordning?
    • Och hur ser det ut om man sätter in dom i omvänd ordning, alltså 5 7 3 6 1 4 2?
    • Är båda träden binära sökträd?
    • Är de balanserade?

    Insättning av 4 2 1 6 3 7 5 ger trädet

                 4
    
           2           6
    
        1     3     5     7 
    
    

    Binärt sökträd: ja
    Balanserat: ja

    Insättning av 5 7 3 6 1 4 2 ger trädet

                 5
    
           3           7
    
        1     4     6       
    
         2
    

    Binärt sökträd: ja
    Balanserat: ja


  4. POSTORDERTRÄD

    • Skriv ut något av träden i inordning och bygg upp ett nytt träd från denna talföljd.
    • Skriv sedan ut dom i preordning och bygg upp nya träd från dessa talföljder.
    • Skriv slutligen ut dom i postorder och bygg upp nya träd från dessa talföljder.

    Inordning + nybygge

    Båda träden ger 1 2 3 4 5 6 7 8 i inordning
    Nya trädet bli en tarm, ytterst obalanserat.

       1
         2
           3
             4
               5
                 6
                   7
    

    Preordning + nybygge Första trädet i preordning ger 4 2 1 3 6 5 7 och nytt träd blir

                 4
    
           2           6
    
        1     3     5     7 
    

    (samma som ursprungsträdet)

    Andra trädet i preorder ger 5 3 1 2 4 7 6 och nytt träd blir

                 5
    
           3           7
    
        1     4     6       
    
         2
    

    (samma som ursprungsträdet)

    Postorder + nybygge

    Första trädet i postorder ger 1 3 2 5 7 6 4 och nytt träd blir

                                                                
                 1                                              
                                                                
                        3                                       
                                                                
                   2         5                                  
                                                                
                          4     7                               
                                                                
                               6                                
    

    Andra trädet i postorder ger 2 1 4 3 6 7 5 och nytt träd blir

                                                                
                 2                                              
                                                                
          1             4                                       
                                                                
                   3         6                                  
                                                                
                          5     7                               
    

    Rekursion

  5. GCD

    För att beräkna största faktorn som två tal m och n har gemensamt kan vi använda Euklides algoritm:

    Om m är jämnt delbar med n så är n den största gemensamma faktorn. Annars är GCD(m, n) = GCD(n, m%n). Skriv en rekursiv funktion!

       def gcd(m, n):
         if m%n == 0:
            return n
         else:
            return gcd(n, m % n)
    

  6. FIBONACCITAL

    Leonardo Fibonacci skrev år 1225 en bok där han beskrev denna intressanta talföljd:
    Sista december föds en kaninpojke och en kaninflicka. Vid två månaders ålder och varje månad därefter producerar varje kaninpar ett nytt kaninpar. Vi kan skriva en rekursiv formel för antal kaninpar:\(f(0)=0\)\(f(1)=1\)\(f(n)=f(n-1) + f(n-2)\)
    Skriv en rekursiv funktion för att beräkna Fibonaccital. Visa vilka rekursiva anrop den ger upphov till vid beräkningen av f(5). Är det här det effektivaste sättet att beräkna Fibonaccitalen?

           def fib(n):
               if n <= 1: 
                  return n
               else:
                  return fib(n-1) + fib(n-2)
    


    Man kan visa att antalet anrop faktiskt växer snabbare än själva Fibonaccitalen!
    (För N=40 är Fibonaccitalet ca hundra miljoner men antalet rekursiva anrop är över 300 miljoner.)
    Bättre vore här att använda en for-slinga:

        def fib(n):
             f0 = 0
             f1 = 1
             for i in range(n-1):
    	      f2 = f1 + f0
    	      f0 = f1
    	      f1 = f2
             return f1
    
    Den här implementationen går i linjär tid, O(n).
  7. REKURSIV TRÄDSUMMA

    Ge en rekursiv tanke för summan av alla talen i trädet och programmera den så att anropet tree.sum() ger rätt svar.

    Rekursiv tanke: Summan är rottalet plus vänsterträdets summa plus högerträdets summa ... men tomt träd har summan noll.

       def summa(p):     # Om den står utanför klassen slipper man self
          if p == None: 
             return 0
          else:
             return int(p.value)+summa(p.left)+summa(p.right)
    
       class Bintree
         - - -
         def sum(self):
           return summa(self.rot)
    

  8. REKURSIV TRÄDHÖJD

    Ge en rekursiv tanke för höjden av ett träd. Höjden är den maximala nivån som nån av trädets noder befinner sig på. Ett träd med bara en rotnod har höjden 0, och ett tomt träd har höjden -1.
    Rekursiv tanke: Höjden är 1 + max(höjden av vänsterträdet, höjden av högerträdet) ...men tomt träd har höjden -1.

       def height(p):
          if p == None: 
             return -1
          else:
             h1 = height(p.left)
             h2 = height(p.right)
             return max(h1,h2) + 1
    

  9. Aliententan 2015-03-20, uppgift 9 (betyg A)

    Samtliga solförmörkelsedatum på jorden under perioden 4000 f.kr. - 4000 e.kr. är insorterade i ett binärt sökträd. Givet en historisk persons födelse och död, beskriv en algoritm som hittar antal solförmörkelser personen potentiellt skulle kunna ha upplevt under sin livstid.
    Algoritmbeskrivningen måste vara välstrukturerad och begriplig.


Teacher Linda Kann created page 8 September 2015