Dynamiskt problem (algoritmer)
Dynamiska problem i beräkningskomplexitetsteori är problem som anges i termer av förändrade indata. I den mest allmänna formen brukar ett problem i denna kategori anges på följande sätt:
- Givet en klass av indataobjekt, hitta effektiva algoritmer och datastrukturer för att svara på en viss fråga om en uppsättning indataobjekt varje gång indata ändras, dvs objekt infogas eller raderas.
Problem i denna klass har följande komplexitetsmått:
- Utrymme – mängden minnesutrymme som krävs för att lagra datastrukturen;
- Initialiseringstid – tid som krävs för den initiala konstruktionen av datastrukturen;
- Insättningstid – tid som krävs för uppdatering av datastrukturen när ytterligare ett indataelement läggs till;
- Borttagningstid – tid som krävs för uppdatering av datastrukturen när ett indataelement raderas;
- Frågetid – tid som krävs för att besvara en fråga;
- Andra operationer som är specifika för problemet i fråga
Den övergripande uppsättningen av beräkningar för ett dynamiskt problem kallas en dynamisk algoritm .
Många algoritmiska problem angivna i termer av fasta indata (kallade statiska problem i detta sammanhang och lösta med statiska algoritmer ) har meningsfulla dynamiska versioner.
Speciella fall
Inkrementella algoritmer , eller onlinealgoritmer , är algoritmer där endast tillägg av element är tillåtna, eventuellt med utgångspunkt från den tomma/triviala indata.
Dekrementella algoritmer är algoritmer där endast raderingar av element är tillåtna, med början med en initiering av en fullständig datastruktur.
Om både tillägg och raderingar är tillåtna kallas algoritmen ibland för fullt dynamisk .
Exempel
Maximalt element
- Statiskt problem
- För en uppsättning av N tal hitta det maximala.
Problemet kan lösas på O(N) tid.
- Dynamiskt problem
- För en initial uppsättning av N nummer, bibehåll dynamiskt det maximala när insättning och radering är tillåtna.
En välkänd lösning på detta problem är att använda ett självbalanserande binärt sökträd . Det tar utrymme O(N), kan initialt konstrueras i tiden O(N log N) och tillhandahåller insättnings-, raderings- och frågetider i O(log N).
- Underhållsproblemet med prioritetskön Det
- är en förenklad version av detta dynamiska problem, där man bara måste ta bort det maximala elementet. Denna version kan göra med enklare datastrukturer.
Grafer
Givet en graf, bibehåll dess parametrar, såsom anslutning, maximal grad, kortaste vägar etc., när infogning och radering av dess kanter är tillåtna.
Se även