Transdikotom modell
I beräkningskomplexitetsteori , och mer specifikt i analysen av algoritmer med heltalsdata , är den transdikotoma modellen en variant av direktåtkomstmaskinen där maskinordstorleken antas matcha problemstorleken. Modellen föreslogs av Michael Fredman och Dan Willard , som valde dess namn "eftersom dikotomien mellan maskinmodellen och problemstorleken korsas på ett rimligt sätt."
I ett problem som heltalssortering där det finns n heltal som ska sorteras, antar den transdikotoma modellen att varje heltal kan lagras i ett enda ord i datorns minne, att operationer på enstaka ord tar konstant tid per operation, och att antalet av bitar som kan lagras i ett log 2n enda ord är minst . Målet med komplexitetsanalysen i denna modell är att hitta tidsgränser som endast beror på n och inte på den faktiska storleken på ingångsvärdena eller maskinorden. Vid modellering av heltalsberäkningar är det nödvändigt att anta att maskinord är begränsade i storlek, eftersom modeller med obegränsad precision är orimligt kraftfulla (kan lösa PSPACE-kompletta problem i polynomtid). Den transdikotoma modellen gör ett minimalt antagande av denna typ: att det finns en viss gräns och att gränsen är tillräckligt stor för att tillåta slumpmässig åtkomstindexering i indata.
Förutom dess tillämpning på heltalssortering har den transdikotoma modellen också tillämpats på utformningen av prioriterade köer och på problem i beräkningsgeometri och grafalgoritmer .
Se även