בסיס אונרי – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ תמונות - הסבה לעברית, תיקון פרמטרים# |
תיקון השטויות שהיו כתובות מקודם |
||
שורה 10:
בשיטה האונרית אין סימן מוסכם המשמש לייצוג [[0 (מספר)|אפס]] כפי שקיים בבסיסי הספירה האחרים - אם הייתה ספרה עבור אפס, הבסיס היה למעשה [[בסיס בינארי|בינארי]], שכן היה מכיל שתי ספרות. לכן לאפס מתייחסים בצורה עקיפה, על ידי אי כתיבת מספר במקום שבו מצפים שיופיע. הדבר אינו ייחודי לשיטה האונרית - גם ב[[שיטת ספירה|שיטות ספירה]] מתקדמות יחסית דוגמת [[ספרות רומיות|הספרות הרומיות]] אין סימן לאפס.
בהשוואה לשיטות ספירה המבוססות על מיקום, שיטת הספירה האונרית היא מסורבלת ולא משתמשים בה עבור חישובים גדולים. עם זאת, לעתים משתמשים בה ב[[מדעי המחשב]] כאשר מדברים על מחלקות סיבוכיות, הסיבה היא שבבסיס אונארי, על מנת לייצג את המספר N - דרושים לנו N תווים, בעוד שבשביל להציג את המספר N בכל בסיס אחר שאינו אונארי, דרושים לנו c*logN תווים, כאשר c הוא קבוע שתלוי בבסיס שנבחר(אך לא ב-N), ההבדל הגדול בין כמות התווים בין בבסיס אונארי לעומת בסיסים אחרים משמש אותנו על מנת לבצע אבחנות לגבי המשאבים שבעיה מסוימת עלולה לדרוש על מנת לפתור אותה, לדוגמא אם האלגוריתם שלנו מקבל כקלט מספר טבעי N ומבצע N צעדים, אזי אם הקלט יכתב בבינארית, מספר הצעדים שהאלגוריתם יעשה הוא מעריכי בגודל הייצוג של הקלט(שכן אנו זקוקים לlogN תווים והאלגוריתם ביצע N צעדים), ואם הקלט יכתב באונארית, מספר הצעדים שהאלגוריתם יעשה הוא לינארי בגודל הייצוג של הקלט, השאלה "איך אנחנו מגדירים לפי איזה בסיס נייצג מספרים" תלויה בבעיה, והיא חלק מהגדרת הבעיה, לעיתים אנו נתקלים בבעיות שנחשבות קשות לפתרון(במובן של כמות משאבים גבוהה) ואז מסתכלים על ה"גרסא האונארית" של הבעיה, בה כל מספר מיוצג בבסיס אונארי, ומגלים שאותו אלגוריתם בדיוק שפעל מקודם בסיבוכיות מעריכית, פועל כעת בסיבוכיות פולינומית, נשים לב שהבעיה עצמה לא השתנתה, וגם לא האלגוריתם, פשוט שינינו את "חוקי המשחק" על ידי הגדרה של איך אנחנו מייצגים את הקלטים, וההחלטה הזו היא חלק מהגדרת הבעיה.
לדוגמה, הבעיה של [[פירוק מספר שלם לגורמים|פירוק מספר לגורמים]] דורשת, ככל הידוע, [[סיבוכיות זמן ריצה|זמן ריצה]] שהוא יותר מאשר [[פולינום|פולינומי]] בגודל הקלט כאשר הקלט הוא מספר הנתון בבסיס בינארי, וגודל הקלט נמדד על פי מספר הספרות (ולכן הוא [[לוגריתם]] על בסיס 2 של המספר עצמו שהועבר). לעומת זאת, אם המספר יועבר בבסיס אונרי, זמן הריצה יהיה לינארי בגודל הקלט (שיהיה שווה במקרה זה לגודל המספר). בצורה זו לא נחסך זמן, אלא פשוט נבחרת דרך אחרת למדוד בה את הסיבוכיות של הבעיה.
| |||