בסיס אונרי – הבדלי גרסאות
תוכן שנמחק תוכן שנוסף
בעיית הפירוק לגורמים אינה NP קשה |
אין תקציר עריכה |
||
שורה 1:
{{ספרות}}
ספירה על '''בסיס אונרי''' היא [[בסיס (לשיטת ספירה)|ספירה לפי בסיס 1]]. זו שיטת הספירה הפשוטה ביותר לייצוג [[מספר טבעי|המספרים הטבעיים]]: כדי לייצג את המספר N, סמל אחד, שנבחר לייצג את 1,
[[תמונה:Unary numeral eight.png|ימין|ממוזער|שיטות שונות לרשום את המספר 8 בבסיס אונרי]]
שורה 13:
לדוגמה, הבעיה של [[פירוק לגורמים|פירוק מספר לגורמים]] דורשת, ככל הידוע, [[סיבוכיות זמן ריצה|זמן ריצה]] שהוא יותר מאשר [[פולינום|פולינומי]] בגודל הקלט כאשר הקלט הוא מספר הנתון בבסיס בינארי, וגודל הקלט נמדד על פי מספר הספרות (ולכן הוא [[לוגריתם]] על בסיס 2 של המספר עצמו שהועבר). לעומת זאת, אם המספר יועבר בבסיס אונרי, זמן הריצה יהיה לינארי בגודל הקלט (שיהיה שווה במקרה זה לגודל המספר). בצורה זו לא נחסך זמן, אלא פשוט נבחרת דרך אחרת למדוד בה את הסיבוכיות של הבעיה.
==ראו גם==
* [[יחידה חוזרת]]
[[קטגוריה: שיטות ספירה]]
| |||