למצוא האם מספר הוא ריבועי בסיבוכיות לוגריתמית

[Sturm Liouville]

למצוא האם מספר הוא ריבועי בסיבוכיות לוגריתמית

נתון מספר שלם n.
ניתן כמובן לענות על השאלה האם n הוא מספר ריבועי בסיבוכיות זמן ((O(sqrt(n .
האם ניתן גם בסיבוכיות לוגריתמית (O(logn ?

 

[FineSilverMan]

כלומר

האם קיים x כך ש:
x^2=n
כלומר:
logx^2=logn
2logx=logn
logx=0.5logn
x=10^0.5logn or x=e^0.5logn
בהתאם לבסיס.
או משהו כזה.

 

[Sturm Liouville]

לא ממש הבנתי מה אתה מציע

סיבוכיות זמן זה במובן של מדעי המחשב...

 

[סיגמה535]

קצת תלוי במודל החישובי, אבל

חיפוש בינארי נותן סיבוכיות פולי-לוגריתמית. אם במודל שלך פעולות כפל וחיבור נעשות בזמן קבוע, אז חיפוש בינארי נותן בדיוק O(logn).

מתחילים עם
low=0
high=n

כל עוד high-low>1
אם n נמצא ממש בין low^2 ל high^2, בודקים איפה נמצא n ביחס לריבוע הממוצע של low ו high.
מעדכנים את low או את high בהתאם.

בסיום הלולאה,
אם n נמצא ממש בין low^2 ל high^2 מחזירים false.
אחרת true.


מספר האיטרציות של הלולאה הוא logn.

 

[Sturm Liouville]

וואלה, נכון...

באמת חשדתי שהפתרון שכתבתי במבחן בסיבוכיות של שורש n, הוא פשוט מידי. הייתי צריך להבין שלא לזה התכוון המשורר...

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

 

[אורי769]

הערה

בדר"כ בתורת הסיבוכיות, סיבוכיות של אלגוריתם מיוצגת כפונקציה של גודל הקלט. אם האלגוריתם שלך הקלט שלו הוא מספר בודד x אז גודל הקלט הוא אורך הייצוג של x. בכל שיטת ייצוג סבירה (נאמר ייצוג בינארי או עשרוני) אורך הייצוג של x הוא פרופורציוני ל-logx. לכן הסיבוכיות של האלגוריתם המדובר היא למעשה לינארית.