איחוד קבוצות זרות – הבדלי גרסאות

למעשה, שימוש בטכניקות שפורטו לעיל יניב [[ניתוח לשיעורין|סיבוכיות משוערכת]] של <math>O(\alpha(n))</math> בלבד לכל פעולה, כאשר <math>\alpha(n)</math> היא [[פונקציה הופכית|הפונקציה ההופכית]] לפונקציה <math>n = f(x) = A(x,x)</math>, כאשר <math>A</math> היא [[פונקציית אקרמן]], הידועה בתכונתה כפונקציה שגדלה מהר מאוד. בתור ההופכית לפונקציית אקרמן, <math>\alpha(n)</math> היא בפועל פחות מ-5 לכל ערך מעשי של <math>n</math>. לדוגמה, המספר <math>9876!</math>, כאשר <math>!</math> הוא אופרטור ה[[עצרת]], הוא בעל 35,164 ספרות ומתקבל <math>\alpha(9876!)=5</math>).

 

 

פרדמן (''Fredman'') וסאקס (''Saks'') הראו בשנת [[1989]] כי <math>\Omega(\alpha(n))</math> עצמים בהכרח זוכים לגישה על ידי פעולה כלשהי על מבנה הנתונים בממוצע. תוצאה זו מראה כי החסם שנמצא הוא [[אופטימיזציה (מתמטיקה)|אופטימלי]] מבחינה [[סימון אסימפטוטי|אסימפטוטית]].{{הערה|1={{Citation |first=M. |last=Fredman |authorlink=Michael Fredman |first2=M. |last2=Saks |title=The cell probe complexity of dynamic data structures |journal=Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing |pages=345–354 |date=May 1989 |quote=Theorem 5: Any CPROBE(log ''n'') implementation of the set union problem requires &Omega;(''m'' &alpha;(''m'', ''n'')) time to execute ''m'' Find's and ''n''&minus;1 Union's, beginning with ''n'' singleton sets. }}}}