פונקציה חשיבה

מתוך ויקיפדיה, האנציקלופדיה החופשית
קפיצה אל: ניווט, חיפוש

בתורת הסיבוכיות, שהיא ענף של מדעי המחשב, פונקציה חשיבה בזמן היא פונקציה f מהמספרים הטבעיים לעצמם, וקיימת מכונת טיורינג שבהינתן קלט n, תשאיר על הסרט שלה בסוף הריצה את הפלט (f(n בזמן ריצה שלא ארוך מ-(f(n. המטרה של הגדרה זו היא לא להתייחס לפונקציות שאין להן חסם עליון על זמן הריצה של מכונות טיורינג.

פונקציה חשיבה בזמן[עריכת קוד מקור | עריכה]

יש שתי הגדרות שונות לפונקציה חשיבה בזמן:

  • פונקציה f תיקרא חשיבה בזמן אם קיים מספר טבעי n0 ומכונת טיורינג M כך שלכל n \ge n_0 בהינתן הקלט 1n (המכיל n פעמים את הספרה 1) תעצור אחרי בדיוק (f(n צעדים.
  • פונקציה f תיקרא חשיבה בזמן אם קיימת מכונת טיורינג M כך שבהינתן המחרוזת 1n תדפיס את הייצוג הבינארי של (f(n בזמן ((O(f(n (ניתן גם להשתמש בייצוג אונרי במקום זאת, היות שניתן לעבור בין השניים בזמן ((O(f(n).

כמו כן, פונקציה f תיקרא חשיבה באופן מלא בזמן אם קיימת מכונת טיורינג M שבהינתן הקלט 1n, תעצור אחרי (f(n צעדים.

פונקציה חשיבה במקום[עריכת קוד מקור | עריכה]

באופן דומה, פונקציה f תיקרא חשיבה במקום אם קיים מספר טבעי n0 ומכונת טיורינג M כך שלכל n \ge n_0 בהינתן הקלט 1n, תדפיס את הפלט (f(n בייצוג בינארי (או אונרי), תוך שימוש בלכל היותר ((O(f(n מקום בסרט.

פונקציה f תיקרא חשיבה באופן מלא במקום אם קיימת מכונת טיורינג M שבהינתן הקלט 1n תעצור אחרי שימוש בבדיוק (f(n תאי סרט.

דוגמאות[עריכת קוד מקור | עריכה]

רוב הפונקציות השימושיות (f(n (כמו n,n^k,2^n) הן חשיבות בזמן ובמקום, כל עוד (f(n היא לפחות cn עבור קבוע c>0. לא קיימת פונקציה שהיא (o(n וחשיבה בזמן, אלא אם כן היא קבועה החל ממקום מסוים, היות שאין מספיק זמן לקרוא את כל הקלט. לעומת זאת, הפונקציה log(n) היא חשיבה במקום.

שימושים[עריכת קוד מקור | עריכה]

נעשה שימוש רב בפונקציות חשיבות בזמן כנגזרת של משפט ההיררכיה בזמן. הן חשובות היות שההיררכיה מסתמכת על מכונת טיורינג שמכריעה שפה בזמן ((O(f(n בעוד שהאלגוריתם לוקח יותר מ(f(n צעדים. זה כמובן לא אפשרי בלי היכולת לחשב את (f(n בזמן הזה. נעשה שימוש בפונקציות חשיבות במקום באופן דומה במשפט ההיררכיה במקום.

ראו גם[עריכת קוד מקור | עריכה]

P Computer-science.png ערך זה הוא קצרמר בנושא מדעי המחשב. אתם מוזמנים לתרום לוויקיפדיה ולהרחיב אותו.