» נושאי לימוד
» נושאי לימוד
יום שבת 4 באפריל 2020
הגדרת סיבוכיות
דף ראשי  ממשיכים לאלגוריתמים 2  הגדרת סיבוכיות גרסה להדפסה

סיבוכיות- הגדרה

 

הגדרה: תהי M מ"ט. נסמן ב-TM(X)  את מספר הצעדים ש-M מבצעת על הקלט X.

  TM(X): ∑*→N U {∞}- זוהי פונקציה שמקבלת מחרוזת ומחזירה את מספר הצעדים

שהמכונה M מבצעת עליה.

נאמר כי M פועלת בסיבוכיות זמן f אם לכל Xε∑* מתקיים: TM(X)≤f(|X|)

ז"א שיש חסם עליון למספר הצעדים שהמכונה עושה.

 

הגדרה: תהי L שפה, ותהי f:N→N . נאמר כי L בעלת סיבוכיות זמן f, אם קיימת מ"ט M שפועלת בסיבוכיות זמן f ו-M מכריעה את L.

 

משפט: תהי {P={x|x=xR שפת הפולינדרומים. אזי במ"ט עם סרט בודד ל-P סיבוכיות זמן

לפחות Ω(n2) .

 

משפט (ההאצה): תהי L שפה כך ש-L בעלת סיבוכיות זמן f.

אזי לכל α > 0 קבוע, L הינה בעלת סיבוכיות זמן αf(n)+4n כאשר n

הינו גודל הקלט.

 

מעניין אותנו α-ים קטנים, למשל ⅓=α . אז אומרים שאם L בעלת סיבוכיות f , אז גם

בעלת סעבוכיות f0.5 , f0.0001 וכן הלאה. ז"א שיש מ"ט אחרת

שיכולה להכריע את L בקבוע קטן יותר, כמובן שטבלת המעברים שלה גדולה יותר.

 

מסקנה: המודל של מכונת טיורינג לא רגיש מספיק בשביל להבחין בין קבועים.

באותו אופן, גם המחשב לא רגיש לקבועים, לכן אנו מדברים על סיבוכיות כזו.

 

 10-02-04 / 09:49  עודכן ,  21-01-04 / 20:15  נוצר ע"י שמרית דויטש  בתאריך 
 ממשיכים לאלגוריתמים 2 - הקודםהבא - הגדרת בעיות P ו- NP 
תגובות הקוראים    תגובות  -  0
דרכונט
מהי מערכת הדרכונט?
אינך מחובר, להתחברות:
דוא"ל
ססמא
נושאי לימוד
חיפוש  |  לא פועל
משלנו  |  לא פועל
גולשים מקוונים: 4