College 8 29-9-2017
Recursief algoritme
- Quicksort
- Merge sort
Je kan de runtme an recursie e algoritmen analyseren. Recursie e algoritmen roepen telkens
opnieuw een methode aan.
Recursi iteit: het optreden an constructe als onderdeel an de identeke soort constructe . en
erschillen doorgaans in waarde. Je herhaalt als het ware een constructee e roept hem opnieuw
aan. Om een gege en probleem op te lossen, roepen algoritmen zichzelf opnieuw aan om zo om te
kunnen gaan met gerelateerde subproblemen. Dit is een di ide-and-conquer benadering: het
probleem wordt opgebroken in subproblemen die li ken op het originele probleem maar dan kleiner.
ls e de oplossingen an de subproblemen combineert heb e de oplossing oor het gehele originele
probleem.
In de informate is er een methode waar de oplossing an een probleem afangt an de oplossingen
an kleinere identeke problemen. Dus geen iteratee
We willen weten hoe eel t d een zeker recursief algoritme kost als functe an in oergroote n.
- Te berekenen door ‘operatess tellen? Je weet niet hoe eel een recursie e aanroep koste
Het optellen an doubles
Torens an Hanoi
R is de rand oorwaarde/basis/bodem
,V is de oortgangs ergeli king
Recurrente betrekking:
Defnieert de waarde an de functe in termen an de functewaardenn oor kleinere parameters.
Ieder getal uit de ri hangt af an zi n directe oorganger en dus indirect an al zi n oorgangers. De
Fibonacci ri is hier een goed oorbeeld an.
De oplossing an een recurrente betrekking geef de waarde rechtstreeks, dus niet in termen an
andere functewaarden.
Een recurrente betrekking exact oplossen
Soms werkt ‘guess and pro es. Dit kun e dus proberen te gokken en er olgens te bewi zen met
inducte.
Voor Merge-Sort kun e dit niet exact oplossen
,Recurrente betrekkingen asymptotscc oplossen
ls e asymptotsch ki kt, negeer e bepaalde aspecten.
- De rand oorwaarde is meestal niet belangri k
- fronden bi delen is niet belangri ke asymptotsch geef dit hetzelfde resultaat
- De waarde an constanten in extra termen is niet belangri k
- Maar: constanten an recursie zi n heel belangri keee Het maakt natuurli k een erschil hoe
aak e de recursie ingaat.
3 metcodes:
Substtutemethode
Je gokt het uiste antwoord en e bewi st dat dit klopt. Dit doe e op een asymptotsche manier, want
de constanten ind e in e bewi s.
Recursieboom
Een analyse an een recursieboom. Dit kun e gebruiken om e ‘guesss te ormen. Je ki kt hoe eel
werk er per ni eau wordt uitge oerd.
Master methode
Voor een speciale orm an een recurrente betrekking
T ( n )=a x T ¿
Maximum subarray probleem
Recursieboom
- Ga per in oer n een ast aantal a keer in recursie
- Op een in oer die een aste fracte /b an de in oer n is
- Doe per ni eau nog fnn werk oor het combineren
, Dan kri g e een recurrente betrekking: T ( n )=a x T ¿
Een recursieboom helpt deze op te lossen door de waarde an Tnn uit te drukken als:
Zie oorbeeld Merge-sort op papiere
Construeren recursieboom: elke knoop representeert de t d die nodig is oor het oplossen an een
deelprobleem op een bepaald ni eau
- In de knoop staat de t d oor het erdelen en combineren fnn
- Tel daarbi op de t d oor a deelproblemen an om ang n/b op een ni eau dieper
- epaal de rekent d recursief totdat e op het ni eau an problemen an om ang bent
gekomen: Tn = fn
i Merge sort: de input op ni eau i is n/2 i, want input n is i keer door 2 gedeeld.
Wanneer is n/2i = ?
- 2i=n
- i = 2 log n = lg n
Er is erdubbeling op elk ni eau an de knopen. Dus het aantal knopen op het laagste ni eau is 2 lg n =
n.
Dus wat is M(n)?
Recursief algoritme
- Quicksort
- Merge sort
Je kan de runtme an recursie e algoritmen analyseren. Recursie e algoritmen roepen telkens
opnieuw een methode aan.
Recursi iteit: het optreden an constructe als onderdeel an de identeke soort constructe . en
erschillen doorgaans in waarde. Je herhaalt als het ware een constructee e roept hem opnieuw
aan. Om een gege en probleem op te lossen, roepen algoritmen zichzelf opnieuw aan om zo om te
kunnen gaan met gerelateerde subproblemen. Dit is een di ide-and-conquer benadering: het
probleem wordt opgebroken in subproblemen die li ken op het originele probleem maar dan kleiner.
ls e de oplossingen an de subproblemen combineert heb e de oplossing oor het gehele originele
probleem.
In de informate is er een methode waar de oplossing an een probleem afangt an de oplossingen
an kleinere identeke problemen. Dus geen iteratee
We willen weten hoe eel t d een zeker recursief algoritme kost als functe an in oergroote n.
- Te berekenen door ‘operatess tellen? Je weet niet hoe eel een recursie e aanroep koste
Het optellen an doubles
Torens an Hanoi
R is de rand oorwaarde/basis/bodem
,V is de oortgangs ergeli king
Recurrente betrekking:
Defnieert de waarde an de functe in termen an de functewaardenn oor kleinere parameters.
Ieder getal uit de ri hangt af an zi n directe oorganger en dus indirect an al zi n oorgangers. De
Fibonacci ri is hier een goed oorbeeld an.
De oplossing an een recurrente betrekking geef de waarde rechtstreeks, dus niet in termen an
andere functewaarden.
Een recurrente betrekking exact oplossen
Soms werkt ‘guess and pro es. Dit kun e dus proberen te gokken en er olgens te bewi zen met
inducte.
Voor Merge-Sort kun e dit niet exact oplossen
,Recurrente betrekkingen asymptotscc oplossen
ls e asymptotsch ki kt, negeer e bepaalde aspecten.
- De rand oorwaarde is meestal niet belangri k
- fronden bi delen is niet belangri ke asymptotsch geef dit hetzelfde resultaat
- De waarde an constanten in extra termen is niet belangri k
- Maar: constanten an recursie zi n heel belangri keee Het maakt natuurli k een erschil hoe
aak e de recursie ingaat.
3 metcodes:
Substtutemethode
Je gokt het uiste antwoord en e bewi st dat dit klopt. Dit doe e op een asymptotsche manier, want
de constanten ind e in e bewi s.
Recursieboom
Een analyse an een recursieboom. Dit kun e gebruiken om e ‘guesss te ormen. Je ki kt hoe eel
werk er per ni eau wordt uitge oerd.
Master methode
Voor een speciale orm an een recurrente betrekking
T ( n )=a x T ¿
Maximum subarray probleem
Recursieboom
- Ga per in oer n een ast aantal a keer in recursie
- Op een in oer die een aste fracte /b an de in oer n is
- Doe per ni eau nog fnn werk oor het combineren
, Dan kri g e een recurrente betrekking: T ( n )=a x T ¿
Een recursieboom helpt deze op te lossen door de waarde an Tnn uit te drukken als:
Zie oorbeeld Merge-sort op papiere
Construeren recursieboom: elke knoop representeert de t d die nodig is oor het oplossen an een
deelprobleem op een bepaald ni eau
- In de knoop staat de t d oor het erdelen en combineren fnn
- Tel daarbi op de t d oor a deelproblemen an om ang n/b op een ni eau dieper
- epaal de rekent d recursief totdat e op het ni eau an problemen an om ang bent
gekomen: Tn = fn
i Merge sort: de input op ni eau i is n/2 i, want input n is i keer door 2 gedeeld.
Wanneer is n/2i = ?
- 2i=n
- i = 2 log n = lg n
Er is erdubbeling op elk ni eau an de knopen. Dus het aantal knopen op het laagste ni eau is 2 lg n =
n.
Dus wat is M(n)?
