כמו מספרי פיבונאצ'י, גם מקדמים בינומיים ניתן לחשב באופן רקורסיבי, על ידי שימוש ביחס:

ⁿc_m = ^n-1c_m-1 + ⁿ^-¹c_m

ניתוח דומה לזה של מספרי פיבונאצ'י מראה כי סיבוכיות הזמן בגישה זו הינה המקדם הבינומי בעצמו. בכל אופן, ידוע כי אם נבנה משולש פסקל, השורה ה- n תיתן את הערכים: C_m,, m=0, n

<TBODY>

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

1 7 21 35 35 21 7 1

</TBODY>

כל כניסה אורכת O(1) זמן חישוב, וישנן O(n²) כאלה. כך שחישוב זה של המקדמים אורך O(n²), אך משתמש ב- O(n²) של שטח זיכרון על מנת לאחסן את המקדמים.

המשך ל: עצי חיפוש בינאריים אופטימליים חזור ל: תוכן עניינים