Transdichotomous modeli - Transdichotomous model
Olarak hesaplama karmaşıklığı teori daha özel olarak, ve algoritma analizi ile tam sayı verileri transdichotomous modeli bir varyasyon rastgele erişim makinesi makinesi içinde kelime büyüklüğü sorunu boy aynı olduğu varsayılır. Model, adını "makine modeli ile problem boyutu arasındaki ikilik makul bir şekilde aşıldığı için" seçen Michael Fredman ve Dan Willard tarafından önerildi .
Sıralanacak n tamsayı olan tamsayı sıralama gibi bir problemde , transdichotomous model, her tamsayının bilgisayar belleğindeki tek bir kelimede saklanabileceğini, tek kelimeler üzerindeki işlemlerin işlem başına sabit zaman aldığını ve sayının tek bir kelimede saklanabilen bitlerin sayısı en az log 2 n'dir . Bu modeldeki karmaşıklık analizinin amacı , girdi değerlerinin veya makine sözcüklerinin gerçek boyutuna değil, yalnızca n'ye bağlı olan zaman sınırlarını bulmaktır . Tamsayı hesaplamasını modellemede, sınırsız kesinliğe sahip modeller makul olmayan bir şekilde güçlü olduğundan ( polinom zamanında PSPACE-tam problemlerini çözebilir) makine kelimelerinin boyutunun sınırlı olduğunu varsaymak gerekir . Transdichotomous model, bu türden minimum bir varsayımda bulunur: bir limit vardır ve limit, girdi verilerine rastgele erişim indekslemeye izin verecek kadar büyüktür.
Transdichotomous model, tamsayı sıralamaya uygulanmasının yanı sıra, öncelik sıralarının tasarımına ve hesaplamalı geometri ve grafik algoritmalarındaki problemlere de uygulanmıştır .
Ayrıca bakınız
Referanslar