ה n בסיבוכיות של חישוב מספר ראשוני
כשמדברים על סיבוכיות של n או n^2 וכדומה בחישוב האם מספר הוא ראשוני, מהו ה-n?
האם זה ערך המספר, מספר הספרות, או מספר הביטים שנדרשים לייצג את המספר כבינארי?
אם לדוגמא, אנו צריכים לבדוק האם ארבעה מיליארד ואחד הוא מספר ראשוני:
אם נקבע את הn לפי ערך המספר, אז n הוא ארבעה מיליארד ואחד.
אם נקבע לפי מספר הספרות, אז n הוא 10.
ואם לפי מספר הביטים, אז n הוא 32.
כשמדברים על סיבוכיות של n או n^2 וכדומה בחישוב האם מספר הוא ראשוני, מהו ה-n?
האם זה ערך המספר, מספר הספרות, או מספר הביטים שנדרשים לייצג את המספר כבינארי?
אם לדוגמא, אנו צריכים לבדוק האם ארבעה מיליארד ואחד הוא מספר ראשוני:
אם נקבע את הn לפי ערך המספר, אז n הוא ארבעה מיליארד ואחד.
אם נקבע לפי מספר הספרות, אז n הוא 10.
ואם לפי מספר הביטים, אז n הוא 32.