Verdel-en-overwin-algoritme

Een zeer populair algoritmisch paradigma, een typisch Verdeel-en-overwin-algoritme lost een probleem op met behulp van de volgende drie stappen:

• Verdelen: Breek het gegeven probleem op in deelproblemen van hetzelfde type.
• Overwin: Los deze subproblemen recursief op
• Combineer: Combineer de antwoorden op de juiste wijze

Volgende zijn enkele standaard algoritmen die verdeel en heers algoritmen zijn:

1 – Binary Search is een zoekalgoritme. In elke stap vergelijkt het algoritme het invoerelement x met de waarde van het middelste element in de array. Als de waarden overeenkomen, wordt de index van het middelste element teruggegeven. Anders, als x minder is dan het middelste element, dan zoekt het algoritme naar de linkerkant van het middelste element, anders naar de rechterkant van het middelste element.

2 – Quicksort is een sorteer-algoritme. Het algoritme kiest een pivot element, herschikt de array elementen op zo’n manier dat alle elementen kleiner dan het gekozen pivot element naar de linkerkant van de pivot gaan, en alle grotere elementen naar de rechterkant. Tenslotte sorteert het algoritme recursief de subarrays links en rechts van het pivot element.

3 – Merge Sort is ook een sorteeralgoritme. Het algoritme verdeelt de array in twee helften, sorteert deze recursief en voegt tenslotte de twee gesorteerde helften samen.

4 – Dichtstbijzijnd Paar Punten: Het probleem is om het dichtstbijzijnde puntenpaar te vinden in een verzameling punten in het x-y vlak. Het probleem kan in O(n²) tijd worden opgelost door de afstanden van elk puntenpaar te berekenen en de afstanden te vergelijken om het minimum te vinden. Het Verdeel en heers algoritme lost het probleem op in O(nLogn) tijd.

5 – Strassen’s Algoritme is een efficiënt algoritme om twee matrices te vermenigvuldigen. Een eenvoudige methode om twee matrices te vermenigvuldigen heeft 3 geneste lussen nodig en is O(n³). Strassen’s algoritme vermenigvuldigt twee matrices in O(n².8974) tijd.

6 – Cooley-Tukey Fast Fourier Transform (FFT) algoritme is het meest gebruikte algoritme voor FFT. Het is een verdeel-en-heers algoritme dat werkt in O(nlogn) tijd.

7 – Karatsuba algoritme voor snelle vermenigvuldiging: Het vermenigvuldigt twee getallen van n cijfers in ten hoogste 3n^(log 3) eencijferige vermenigvuldigingen in het algemeen (en precies n^(log3) wanneer n een macht van 2 is). Het is dus sneller dan het klassieke algoritme, dat n² eencijferige producten vereist.

Telling Inversies Probleem

We zullen een probleem beschouwen dat zich voordoet bij de analyse van ranglijsten, die belangrijk worden voor een aantal huidige toepassingen. Bijvoorbeeld, een aantal sites op het Web maken gebruik van een techniek die bekend staat als collaborative filtering, waarbij ze proberen uw voorkeuren (voor boeken, films, restaurants) te matchen met die van andere mensen op het Internet. Zodra de website mensen met een “soortgelijke” smaak als de uwe heeft geïdentificeerd – op basis van een vergelijking van hoe u en zij verschillende dingen beoordelen – kan hij nieuwe dingen aanbevelen die deze andere mensen leuk hebben gevonden. Een andere toepassing is het gebruik van zoekmachines op het Web, die dezelfde zoekopdracht uitvoeren op veel verschillende zoekmachines en dan proberen de resultaten samen te stellen door te zoeken naar overeenkomsten en verschillen tussen de verschillende ranglijsten die de zoekmachines teruggeven.

Een kernprobleem bij dit soort toepassingen is het probleem van het vergelijken van twee ranglijsten. Je rangschikt een set van rt-films, en dan raadpleegt een collaboratief filtersysteem zijn database om te zoeken naar andere mensen die “soortgelijke” rangschikkingen hadden. Maar wat is een goede manier om numeriek te meten hoe gelijksoortig de rangschikkingen van twee mensen zijn? Het is duidelijk dat een identieke rangschikking erg op elkaar lijkt, en een volledig omgekeerde rangschikking erg verschillend is; we willen iets dat door het middengebied interpoleert.

Laten we eens kijken naar het vergelijken van jouw rangschikking en die van een vreemde over dezelfde set van n films. Een natuurlijke methode zou zijn om de films van 1 tot n te rangschikken volgens jouw rangschikking, vervolgens deze labels te rangschikken volgens de rangschikking van de vreemdeling, en dan te zien hoeveel paren “niet in orde” zijn. Meer concreet beschouwen we het volgende probleem. We krijgen een rij van n getallen a1, …, an; we nemen aan dat alle getallen verschillend zijn. We willen een maat definiëren die ons vertelt hoe ver deze rij van een oplopende volgorde afstaat; de waarde van de maat moet 0 zijn als a1 < a2 << an, en moet toenemen naarmate de getallen onoverzichtelijker worden.

Een natuurlijke manier om dit begrip te kwantificeren is door het aantal inversies te tellen. We zeggen dat twee indexen i < j een inversie vormen als ai > aj, dat wil zeggen, als de twee elementen ai en aj “uit volgorde” zijn. We zullen proberen het aantal inversies te bepalen in de rij a1, …, an.