שיחה:יעילות אלגוריתמית

תהיה ביחס למשפט האחרון בערך

המשפט קובע -

"באופן זה, לדוגמא, אלגוריתם אשר נדרש לפרק מספר ראשוני לגורמיו נדרש לזמן ריצה שהוא לוגריתמי בגודל המספר עצמו."

משפט זה לא ברור לי מכמה סיבות -

1. אם נתון שהמספר ראשוני, מה הטעם לפרק אותו לגורמים בכלל?
2. אם הכוונה הייתה לפרק מספר כלשהו לגורמים ראשוניים - האם לא ראוי להסביר איך יפעל האלגוריתם המדובר ומדוע זוהי סיבוכיותו? (סיבוכיות הפתרון הראשון שעולה בראשי לפתרון הבעיה היא $\ \Theta (n^{1/2})$ - לדעתי - ולוגריתמית במקרה הטוב (אם למשל מדובר בחזקה שלמה של 2))
3. האם ב"גודל המספר" הכוונה לגודל n או לגודל שהמספר תופס בזכרון? ($\ lgn$)

יובל מדר

1. הכותב התכוון כנראה לאלגוריתם שמפרק מספר לגורמיו הראשוניים.
2. האלגוריתם הטוב ביותר שידוע היום לפירוק מספרים עובד בסיבוכיות שהביטוי שמתאר אותה הוא די מסובך, אבל היא בוודאי לא לוגריתמית. בכל מקרה, יידרשו לא מעט סדרות של מאמרים כדי להסביר את האלגוריתם הזה.
3. אני מקווה שהכותב יואיל לשתף איתנו את האלגוריתם שלו לפירוק מספרים בזמן לוגריתמי. רק כדי להיות בטוח, אני מפסיק מעכשיו להשתמש ב-RSA.
4. בקיצור, משפט מיותר, אם חייבים שם דוגמה אפשר למצוא אחרת.

פכידרם 17:45, 30 יולי 2005 (UTC)

2. אני אוכל את הכובע, בויקי האנגלית יש מאמר די קצר על האלגוריתם הזה. אם הוא מובן או לא זה כבר סיפור אחר (אולי אתה תוכל לענות על השאלה).

פכידרם 17:52, 30 יולי 2005 (UTC)

תודה לך. :) יובל מדר

תהיה על השכתוב

"חישוב יעיל לא מתייחס לזמן פולינומיאלי או לא, אלא לחסם התיאורטי על יעילות האלגוריתם"!? זאת אמירה חסרת משמעות, החסם התיאורטי הוא לגבי הסיבוכיות של האלגורתים, החישוב הוא יעיל אם הוא פולינומיאלי. יכול להיות שיש בעיה עם הערך, אבל הנוסח של ההודעה פשוט לא הגיוני. טרול רפאים 11:14, 5 אוגוסט 2005 (UTC)