בסיס אונרי – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
מ בויקיפדיה העברית הנוהג הוא לשים את הקישור לאנגלית למעלה |
מ עוד תיקון קטן |
||
שורה 10:
בשיטה האונרית אין סימן מוסכם המשמש לייצוג [[אפס]] כפי שקיים בבסיסי הספירה האחרים - אם הייתה ספרה עבור אפס, הבסיס היה למעשה [[בסיס בינארי|בינארי]], שכן היה מכיל שתי ספרות. לכן לאפס מתייחסים בצורה עקיפה, על ידי אי כתיבת מספר במקום שבו מצפים שיופיע. הדבר אינו ייחודי לשיטה האונרית - גם ב[[שיטת ספירה|שיטות ספירה]] מתקדמות יחסית דוגמת [[ספרות רומיות|הספרות הרומיות]] אין סימן לאפס.
בהשוואה לשיטות ספירה המבוססות על מיקום, שיטת הספירה האונרית היא מסורבלת ולא משתמשים בה עבור חישובים גדולים. עם זאת, לעתים משתמשים בה ב[[מדעי המחשב]] לתיאור בעיות מסוימות, וזאת על מנת להגדיל באופן "מלאכותי" את גודל הקלט של הבעיה, ובכך להפוך אותה לשייכת למחלקה [[P (מדעי המחשב)|P]].
לדוגמה, הבעיה של [[פירוק לגורמים|פירוק מספר לגורמים]] דורשת (בהנחה כי [[P=NP|P≠NP]]) [[זמן ריצה]] שהוא יותר מאשר [[פולינום|פולינומיאלי]] בגודל הקלט כאשר הקלט הוא מספר הנתון בבסיס בינארי, וגודל הקלט נמדד על פי מספר הספרות (ולכן הוא [[לוגריתם]] על בסיס 2 של המספר עצמו שהועבר). לעומת זאת, אם המספר יועבר בבסיס אונרי, זמן הריצה יהיה לינארי בגודל הקלט (שיהיה שווה במקרה זה לגודל המספר). בצורה זו לא נחסך זמן, אלא פשוט נבחרת דרך אחרת למדוד בה את הסיבוכיות של הבעיה.
| |||