שלום, מספר סטודנטים שאלו אותי את אותה השאלה לגבי זמן הריצה בסעיף מדידות בתרגיל 2.
בשאלה "מהו זמן הריצה הכולל של $m$ פעולות כפונקציה של $m$" הכוונה היא לחסם אסימטוטי.
כלומר, זוהי שאלה תאורטית ולא באמת מדידה, היא נועדה בשביל לוודא שהבנתם את המטלה.
זמן ריצה בסעיף המעשי
Forum
» Forums / שיעורי בית
» זמן ריצה בסעיף המעשי
זמן ריצה בסעיף המעשי
Yahav 13 Jan 2011 12:35
צריך להוכיח שהחסמים של הסיבוכיות של הפעולות שכתבנו ושל הסדרה מהשאלה התאורטית הם
theta
ולא רק
O
?
חייבים להראות גם חסם תחתון או שמספיק עליון?
גם בשאלה התאורטית?
כי כתוב למצוא סדרה כך שזמן הריצה לפעולה הוא theta(logm)
ואם הניתוח של הפעולות הוא רק O זה בעייתי..
ראינו שאלות דומות בתרגול.
את צריכה להראות שפעולה לוקחת זמן ריצה מסוים.
כדי להוכיח שזה אכן זמן הריצה, את צריכה להראות תטא.
זאת מכיוון ש-או גדול הוא רק חסם מלמעלה, הוא לא מראה
שזה אכן זמן הריצה לפעולה.
שימי לב, מה שאת מראה כאן זה לא חסם תחתון כמו שהראנו
לבעיות כמו מיון וכו', אלא זה ניתוח של כמה זמן לוקחת פעולה
מסויימת בפועל.
כמו למשל בשאלה שלוש בתרגיל 5.
(אמנם שם מדובר על סדרת פעולות, אבל זה אותו עקרון)
תראי גם שהתטא רשומה בשאלה מפורש.
/forum/t-298149/#post-