עץ פורש מינימלי – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
אין תקציר עריכה |
|||
שורה 23:
ו-<math> \alpha(m,n) = \min\{i \geq 1 : A(i,\lfloor m/n \rfloor) \geq \log_2 n\}</math> היא [[פונקציית אקרמן|פונקציית אקרמן ההפוכה]].
מהו האלגוריתם המהיר ביותר לפתרון בעיה זו? זוהי אחת השאלות הפתוחות הישנות ביותר בתחום [[מדעי המחשב]]. אם משקלי הקשתות הינם [[מספר שלם|מספרים שלמים]] המוגבלים במספר הביטים המייצגים אותם, אזי ידועים אלגוריתמים מוחלטים (דטרמיניסטיים - שאינם פועלים באקראיות) עם זמן ריצה לינארי <math>\ O(m)</math>. עבור משקלים כלליים, ידועים [[אלגוריתם אקראי|אלגוריתמים אקראיים]] הרצים בזמן הצפוי להיות לינארי.
==קישורים חיצוניים==
| |||