עבודה 6 - שאלה 6 סעיף ב - המרת בסיסים

מנהל: TA_Isana

שלח תגובה
vayness
הודעות: 8
הצטרף: 13:28 10/12/2009

עבודה 6 - שאלה 6 סעיף ב - המרת בסיסים

שליחה על ידי vayness » 17:49 15/06/2010

שלום,
1. האם ניתן להמיר את המספרים המתקבלים בבסיס k (כלומר מספר בעל k ספרות) לבסיס אחר?
2. במידה וכן, האם ניתן להניח כי קיים אלגוריתם הממיר מספר בבסיס כלשהו לבסיס אחר בזמן (1)O?
3. האם יעילות האלגוריתם נמדדת לפי החסם האסימפטוטי על זמן הריצה שלו או לפי זמן הריצה שלו תוך התחשבות במקדמים?
כלומר, האם אלגוריתם שזמן הריצה שלו הוא 4n טוב יותר מאלגוריתם שזמן הריצה שלו הוא 5n, או שמבחינת היעילות הנמדדת בתרגיל הם שקולים?
אשמח לתשובה מהמתרגל האחראי,
תודה

TA_Yakim
הודעות: 53
הצטרף: 19:54 03/06/2010

Re: עבודה 6 - שאלה 6 סעיף ב - המרת בסיסים

שליחה על ידי TA_Yakim » 17:00 16/06/2010

1. כן. זה חשיבה טובה ויותר ממה שציפיתי, מספיק טוב אם תפתרו את זה גם ללא שינויי בסיס
2. לא
3. זמן ריצה אסימפטוטי. (אלא אם מצוין מפורשות, מה שלא יקרה הרבה, בניתוח זמן ריצה, נדרש זמן ריצה אסימפטוטי במקרה הגרוע. אין חשיבות למקדמים)

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

TA_Yakim
הודעות: 53
הצטרף: 19:54 03/06/2010

Re: עבודה 6 - שאלה 6 סעיף ב - המרת בסיסים

שליחה על ידי TA_Yakim » 17:03 16/06/2010

לא שאלת אבל אוסיף גם שניתן להניח שהשוואה בין שני מספרי ת.ז. היא ב o(1) time (עבור המקרים בהם תבחרו להשתמש באלגוריתם מבוסס השוואות)

שלח תגובה

חזור אל “- מבני נתונים 2010”