שיחה:אלגוריתם שור

1. להעביר לפירוק קוונטי. 2. לציין בפסקת המבוא שמדובר באלגוריתם המיועד למחשב היפותטי. עוזי ו. - שיחה 21:38, 27 ביולי 2009 (IDT)

אולי להעביר לאלגוריתם שור (בדומה לאלגוריתם גרובר ואלגוריתם דויטש-ג'וזה)? ולשים הפניות מתאימות? Gran - שיחה 21:45, 27 ביולי 2009 (IDT)

אני בעד. עוזי ו. - שיחה 21:50, 27 ביולי 2009 (IDT)

קירוב לסיבוכיות

הסיבוכיות של האלגוריתמים הקלאסיים כתובה בצורה קצת מסובכת... מה הקירוב שלה? פי כמה הסיבוכיות של אלגוריתם שור קטנה ממנה? (לדעתי, כדאי להוסיף את התשובות לשתי שאלות אלה לתוך הערך) 84.109.248.104 20:38, 1 באוגוסט 2013 (IDT)

איך נוסחת הסיבוכיות שהובאה לגבי האלגוריתמים הלא קוואנטיים יכולה לחרוג מפולינום?

אם e מועלה בחזקה של logn זה שקול לn. המעריך לכאורה נמוך מlogn (כי ((log(log n) נמוך מ (log n)

אם הכוונה ל log על בסיס 2 עדיין זה לא אמור לחרוג מn בריבוע.

איפה טעיתי?

אריק1111 - שיחה 22:52, 22 במרץ 2014 (IST)

מקובל למדוד סיבוכיות ביחס לאורך המחרוזת. מספר טבעי n מיוצג על ידי הייצוג העשרוני (או הבינארי, אין חשיבות לבסיס) שלו, כלומר על ידי מחרוזת שאורכה בערך log n. לכן מאלגוריתם יעיל אנו דורשים שיהיה פולינומי ביחס ל-log n, ולא ביחס ל-n. דניאל • תרמו ערך 23:05, 22 במרץ 2014 (IST)