| Het bepalen van de efficiëntie van een algoritme omvat het analyseren van de tijdcomplexiteit ervan en ruimtecomplexiteit . Dit helpt ons te begrijpen hoe het bronnengebruik van het algoritme (tijd en geheugen) schaalt met de grootte van de invoer. Hier is een overzicht van de computerprocedure:
1. Begrijp tijdcomplexiteit en ruimtecomplexiteit:
* Tijdcomplexiteit: Meet de hoeveelheid tijd die een algoritme nodig heeft om te voltooien als een functie van de invoergrootte (vaak aangeduid als 'n'). We zijn geïnteresseerd in *hoe* de uitvoeringstijd toeneemt, niet de exacte tijd in seconden.
* Ruimtecomplexiteit: Meet de hoeveelheid geheugen (of ruimte) die een algoritme nodig heeft als functie van de invoergrootte 'n'. Dit omvat de ruimte voor invoergegevens en eventuele aanvullende gegevensstructuren die door het algoritme worden gebruikt.
2. Belangrijke bewerkingen identificeren:
* Basisbewerkingen: Identificeer de bewerkingen die aanzienlijk bijdragen aan de uitvoeringstijd. Deze kunnen het volgende omvatten:
* Rekenkundige bewerkingen (+, -, \*, /, %)
* Vergelijkingen (<,>, ==, !=)
* Opdrachten (=)
* Array-toegangen (arr[i])
* Geheugentoewijzingen en deallocaties (afhankelijk van de taal)
* Focus op dominante activiteiten: Sommige operaties zullen veel vaker worden uitgevoerd dan andere. Concentreer u op deze *dominante* bewerkingen, omdat deze de grootste impact zullen hebben op de algehele looptijd. In een sorteeralgoritme zijn vergelijkingen en swaps bijvoorbeeld dominant.
3. Analyseer de structuur van het algoritme (code-walkthrough):
* Opeenvolgende verklaringen: Verklaringen die in volgorde worden uitgevoerd, dragen een constante hoeveelheid tijd of ruimte bij.
* Lossen: De tijdscomplexiteit van een lus hangt af van hoe vaak deze itereert:
* Eenvoudige lus (lineair): `for i in range(n):...` Voert 'n' keer uit, dus de complexiteit is O(n).
* Geneste lussen (kwadratisch, kubisch, etc.): `for i in range(n):for j in range(n):...` Voert 'n * n' keer uit, dus de complexiteit is O(n^2).
* Lus met logaritmisch gedrag: `terwijl n> 1:n =n // 2` Voert log2(n) keer uit, dus de complexiteit is O(log n).
* Lus met afhankelijkheid van innerlijke logica: Analyseer het lichaam van de lus om de complexiteit ervan te bepalen en vermenigvuldig deze met het aantal iteraties.
* Voorwaardelijke uitspraken (if/else):
* Analyseer zowel de 'if'- als de 'else'-blokken. De algehele complexiteit is het *maximum* van de complexiteit van de 'if'- en 'else'-blokken.
* Voor diep geneste 'if/else'-structuren traceert u zorgvuldig de mogelijke uitvoeringspaden.
* Recursie:
* Identificeer de basisscenario('s): Deze beëindigen de recursie.
* Identificeer de recursieve stap: Hoe het probleem wordt opgesplitst in kleinere deelproblemen.
* Schrijf een herhalingsrelatie: Dit beschrijft wiskundig de tijdscomplexiteit van de recursieve functie. Bijvoorbeeld:`T(n) =T(n/2) + O(1)` (binair zoeken)
* Los de herhalingsrelatie op: Gebruik methoden zoals de hoofdstelling, substitutie of recursieboom om de asymptotische tijdscomplexiteit te vinden.
* Functieoproepen: Houd rekening met de tijdscomplexiteit van de aangeroepen functie. Als een functie 'A' functie 'B' aanroept, zal de tijdscomplexiteit van 'A' de tijdscomplexiteit van 'B' omvatten.
4. Druk complexiteit uit in asymptotische notatie (Big O, Big Omega, Big Theta):
* Grote O-notatie (O): Vertegenwoordigt de *bovengrens* van de groeisnelheid van het algoritme. Het beschrijft het *worst-case* scenario. "De tijdcomplexiteit van het algoritme is O(n^2)" betekent dat de looptijd van het algoritme niet *sneller* zal groeien dan n^2 naarmate 'n' toeneemt.
* Grote Omega-notatie (Ω): Vertegenwoordigt de *ondergrens* van de groeisnelheid van het algoritme. Het beschrijft het *best-case* scenario. "De tijdcomplexiteit van het algoritme is Ω(n)" betekent dat de looptijd van het algoritme niet *langzamer* zal groeien dan 'n' naarmate 'n' toeneemt.
* Grote Theta-notatie (Θ): Vertegenwoordigt de *strakke grens* van de groeisnelheid van het algoritme. Het beschrijft het gemiddelde scenario en wanneer de looptijd van het algoritme in hetzelfde tempo groeit als de functie. "De tijdcomplexiteit van het algoritme is Θ(n log n)" betekent dat de looptijd van het algoritme in hetzelfde tempo zal groeien als n log n.
Veel voorkomende tijdcomplexiteiten (in het slechtste geval, Big O):
* O(1):Constante tijd: De uitvoeringstijd is onafhankelijk van de invoergrootte. Voorbeeld:toegang krijgen tot een element in een array via zijn index.
* O(log n):Logaritmische tijd: De uitvoeringstijd neemt logaritmisch toe met de invoergrootte. Voorbeeld:binair zoeken in een gesorteerde array.
* O(n):Lineaire tijd: De uitvoeringstijd neemt lineair toe met de invoergrootte. Voorbeeld:Zoeken naar een element in een ongesorteerde array.
* O(n log n):Linearitmische tijd: Vaak voorkomend in efficiënte sorteeralgoritmen. Voorbeeld:Samenvoegsortering, Quicksort (gemiddeld geval).
* O(n^2):Kwadratische tijd: De uitvoeringstijd neemt kwadratisch toe met de invoergrootte. Voorbeeld:Bellen sorteren, Invoeg sorteren.
* O(n^3):Kubieke tijd: Voorbeeld:Matrixvermenigvuldiging.
* O(2^n):Exponentiële tijd: De uitvoeringstijd verdubbelt bij elke toevoeging aan de invoergrootte. Duidt vaak op een brute-force aanpak. Voorbeeld:alle mogelijke subsets van een set proberen.
* O(n!):Factoriële tijd: De uitvoeringstijd groeit extreem snel. Voorbeeld:alle permutaties van een set vinden.
5. Negeer constante factoren en termen van lagere orde:
Bij het gebruik van asymptotische notatie zijn we vooral geïnteresseerd in de *dominante* term die de groeisnelheid bepaalt. Constante factoren en termen van lagere orde worden onbelangrijk naarmate 'n' erg groot wordt.
* `3n^2 + 5n + 10` wordt vereenvoudigd tot `O(n^2)`
* `100 log n + n` is vereenvoudigd tot `O(n)` (n groeit sneller dan log n)
* `2^n + n^5` wordt vereenvoudigd tot `O(2^n)`
6. Analyseer de complexiteit van de ruimte:
Analyseer, net als bij tijdcomplexiteit, de ruimte die door het algoritme wordt gebruikt. Overwegen:
* Invoerruimte: De ruimte die nodig is om de invoergegevens op te slaan.
* Extra ruimte: De extra ruimte die door het algoritme wordt gebruikt, buiten de invoerruimte, voor variabelen, datastructuren en recursie-oproepstapel.
Voorbeelden:
* Lineair zoeken:
```python
def lineaire_zoekopdracht(arr, doel):
voor ik binnen bereik(len(arr)):
als arr[i] ==doel:
retour ik
retour -1
```
* Tijdcomplexiteit: O(n) (lineair, slechtste geval:doel bevindt zich niet in de array of is het laatste element)
* Ruimtecomplexiteit: O(1) (constant, omdat er slechts een paar extra variabelen worden gebruikt)
* Binair zoeken:
```python
def binary_search(arr, doel):
laag =0
hoog =len(arr) - 1
terwijl laag <=hoog:
midden =(laag + hoog) // 2
if arr[mid] ==doel:
midden terug
elif arr[mid]
laag =midden + 1
anders:
hoog =midden - 1
retour -1
```
* Tijdcomplexiteit: O(log n) (logaritmisch)
* Ruimtecomplexiteit: O(1) (constante, iteratieve versie)
* Recursief binair zoeken:
```python
def binary_search_recursive(arr, doel, laag, hoog):
indien laag> hoog:
retour -1
midden =(laag + hoog) // 2
if arr[mid] ==doel:
midden terug
elif arr[mid]
return binary_search_recursive(arr, target, mid + 1, high)
anders:
return binary_search_recursive(arr, target, low, mid - 1)
```
* Tijdcomplexiteit: O(logboek n)
* Ruimtecomplexiteit: O(log n) vanwege recursiediepte. Elke recursieve oproep voegt een nieuw frame toe aan de oproepstapel.
Samengevat:
1. Definieer wat u wilt meten: Tijdcomplexiteit, ruimtecomplexiteit, of beide.
2. Identificeer de belangrijkste bewerkingen bijdragen aan het gebruik van hulpbronnen.
3. Analyseer de structuur van het algoritme (lussen, conditionals, recursie).
4. Toon de complexiteit met behulp van de Big O-, Big Omega- of Big Theta-notatie.
5. Negeer constante factoren en termen van lagere orde.
Door deze stappen te volgen, kunt u de efficiëntie van algoritmen effectief analyseren en het meest geschikte algoritme voor uw specifieke behoeften kiezen. Houd er rekening mee dat het beste algoritme afhangt van het specifieke probleem, de omvang van de invoergegevens en de beschikbare bronnen. |
