In deze tutorial leer je wat asymptotische notaties zijn. Ook leer je over de Big-O-notatie, Theta-notatie en Omega-notatie.
De efficiëntie van een algoritme hangt af van de hoeveelheid tijd, opslag en andere middelen die nodig zijn om het algoritme uit te voeren. De efficiëntie wordt gemeten met behulp van asymptotische notaties.
Een algoritme heeft mogelijk niet dezelfde prestaties voor verschillende soorten invoer. Met de toename van de invoergrootte zullen de prestaties veranderen.
De studie van verandering in prestaties van het algoritme met de verandering in de volgorde van de invoergrootte wordt gedefinieerd als asymptotische analyse.
Asymptotische notaties
Asymptotische notaties zijn de wiskundige notaties die worden gebruikt om de looptijd van een algoritme te beschrijven wanneer de invoer neigt naar een bepaalde waarde of een grenswaarde.
Bijvoorbeeld: bij het sorteren van bellen, wanneer de invoerarray al is gesorteerd, is de tijd die het algoritme nodig heeft lineair, dwz het beste geval.
Maar als de invoerarray in omgekeerde toestand verkeert, heeft het algoritme de maximale tijd (kwadratisch) nodig om de elementen te sorteren, dwz in het ergste geval.
Als de invoerarray niet gesorteerd of in omgekeerde volgorde is, kost het gemiddelde tijd. Deze looptijden worden aangeduid met asymptotische notaties.
Er zijn hoofdzakelijk drie asymptotische notaties:
- Big-O-notatie
- Omega-notatie
- Theta-notatie
Big-O-notatie (O-notatie)
Big-O-notatie vertegenwoordigt de bovengrens van de looptijd van een algoritme. Het geeft dus de moeilijkste complexiteit van een algoritme.
Big-O geeft de bovengrens van een functie
O (g (n)) = (f (n): er bestaan positieve constanten c en n 0 zodat 0 ≦ f (n) ≦ cg (n) voor alle n ≧ n 0 )
De bovenstaande uitdrukking kan worden beschreven als een functie die f(n)bij de verzameling hoort O(g(n))als er een positieve constante bestaat czodat deze tussen 0en cg(n), voor voldoende groot, ligt n.
Voor elke waarde van noverschrijdt de looptijd van een algoritme de tijd die wordt geboden door O(g(n)).
Omdat het de slechtste looptijd van een algoritme geeft, wordt het veel gebruikt om een algoritme te analyseren, omdat we altijd geïnteresseerd zijn in het slechtste scenario.
Omega-notatie (Ω-notatie)
Omega-notatie vertegenwoordigt de ondergrens van de looptijd van een algoritme. Het biedt dus de beste complexiteit van een algoritme.
Omega geeft de ondergrens van een functie
Ω (g (n)) = (f (n): er bestaan positieve constanten c en n 0 zodanig dat 0 ≦ cg (n) ≦ f (n) voor alle n ≧ n 0 )
De bovenstaande uitdrukking kan worden beschreven als een functie die f(n)tot de verzameling behoort Ω(g(n))als er een positieve constante bestaat czodat deze erboven ligt cg(n), voor voldoende groot n.
Voor elke waarde van nwordt de minimumtijd vereist door het algoritme gegeven door Omega Ω(g(n)).
Theta-notatie (Θ-notatie)
Theta-notatie omvat de functie van boven en van onderen. Omdat het de boven- en ondergrens van de looptijd van een algoritme vertegenwoordigt, wordt het gebruikt voor het analyseren van de gemiddelde complexiteit van een algoritme.
Theta begrenst de functie binnen constantenfactoren
Een functie g(n), Θ(g(n))wordt gegeven door de relatie:
Θ (g (n)) = (f (n): er bestaan positieve constanten c 1 , c 2 en n 0 zodat 0 ≦ c 1 g (n) ≦ f (n) ≦ c 2 g (n) voor alle n ≧ n 0 )
De bovenstaande uitdrukking kan worden beschreven als een functie die f(n)tot de verzameling behoort Θ(g(n))als er positieve constanten bestaan en zodanig dat deze kan worden ingeklemd tussen en , voor voldoende grote n.c1c2c1g(n)c2g(n)
Als een functie f(n)ergens tussenin en voor iedereen ligt , dan wordt gezegd dat deze asymptotisch nauw verbonden is.c1g(n)c2g(n)n ≧ n0f(n)
