Stor O-notasjon

Stor O-notasjon er en matematisk notasjon som gir en asymptotisk tilnærming til en funksjon 
  
    
      
        g
        (
        x
        )
      
    
    {\displaystyle g(x)}
  , og skrives ofte 
  
    
      
        O
        (
        g
        (
        x
        )
        )
      
    
    {\displaystyle O(g(x))}
  . Formålet er å kunne gi en enkel og grov beskrivelse av utviklingen til funksjonen 
  
    
      
        g
        (
        x
        )
      
    
    {\displaystyle g(x)}
   når x øker. Mer presist blir symbolet 
  
    
      
        O
      
    
    {\displaystyle O}
   brukt til å beskrive en asymptotisk øvre grense for en funksjon ved hjelp av en, som oftest, enklere funksjon. Det er også andre symboler o, Ω, ω, and Θ for å beskrive forskjellige andre asymptotiske grenser. Stor O-notasjon blir spesielt brukt i kompleksitetsteori, en del av informatikken som sier noe om ressursbruken til en algoritme.
Uttrykket 
  
    
      
         
        f
        (
        x
        )
        =
        O
        (
        g
        (
        x
        )
        )
      
    
    {\displaystyle \ f(x)=O(g(x))}
  , eventuelt 
  
    
      
         
        f
        ∈
        O
        (
        g
        )
      
    
    {\displaystyle \ f\in O(g)}
  , betyr at 
  
    
      
         
        f
        (
        x
        )
      
    
    {\displaystyle \ f(x)}
   for store verdier av 
  
    
      
         
        x
      
    
    {\displaystyle \ x}
   alltid er mindre enn 
  
    
      
         
        c
        g
        (
        x
        )
      
    
    {\displaystyle \ cg(x)}
  , der c er en konstant. En annen måte å skrive det på, er 

  
    
      
        
          lim sup
          
            x
            →
            ∞
          
        
        
          |
          
            
              
                f
                (
                x
                )
              
              
                g
                (
                x
                )
              
            
          
          |
        
        <
        ∞
        .
      
    
    {\displaystyle \limsup _{x\to \infty }\left|{\frac {f(x)}{g(x)}}\right|<\infty .}
  

Fordelen med en slik notasjon, er at det går an å forenkle kompleksitetsanalysen, uten å få alt for store feil. For eksempel er 
  
    
      
        
          x
          
            3
          
        
        +
        100
        
          x
          
            2
          
        
        ∈
        O
        (
        
          x
          
            3
          
        
        )
      
    
    {\displaystyle x^{3}+100x^{2}\in O(x^{3})}
  , da 100x2 er forsvinnende liten i forhold til x3 når x er stor.
Grensen er ikke streng; g kan godt vokse mye raskere enn f. Hvis de vokser like raskt, det vil si at 
  
    
      
        f
        ∈
        O
        (
        g
        )
        ,
        g
        ∈
        O
        (
        f
        )
      
    
    {\displaystyle f\in O(g),g\in O(f)}
  , sier vi at 
  
    
      
        f
        ∈
        Θ
        (
        g
        )
      
    
    {\displaystyle f\in \Theta (g)}
  .


== Relaterte notasjoner ==


== Vanlige klasser av funksjoner ==
Her er en liste over klasser av funksjoner som en ofte støter på ved analyse av algoritmer. De beskriver tidsforbruket til algoritmer når n øker mot uendelig. Funksjonene er listet med økende kompleksitet. c er en vilkårlig konstant.