2 שאלות באלגוריתמים (FFT בעיקר)

[yythe1]

2 שאלות באלגוריתמים (FFT בעיקר)

שאלה ראשונה יש לי כיוון , אני רוצה לדעת אם זה נכון : 1 - להציב את x0 ולקבל את r - סיבוכיות O_n 2 - לסדר את המשוואה כך שנגדיר את q_x (סה"כ יש לבצע חיסור של המספר החופשי מהמשוואה של A_x ולאחר מכן לחלק בx-x0) 3 - על סמך סעיף 2 - לבצע חלוקת פולינומים - סיבוכיות O_n הבעיה היא שאני לא בדיוק השתמשתי פה ב-FFT ולכן זה מוזר לי . שאלה שנייה אין לי שמץ . אשמח לקבל רעיונות או משהו . תודה

 

[1ca1]

לומד בעברית?

לגבי 2 נגידר A(x),B(x) פולינומים מדרגה 15^n כך שהמקדם המתאים הוא 1 אם ai שייך לA, ו0 אחרת. כעת כאשר נקבל את פולינום המכפלה, מקדמיו יהיו Ck=sigma(ai*b(k-i)) zz כעת ע"י מעבר על Ck עבור k בין 0 ל15n תוכל לדעת האם האיבר בקבוצה או לא, וגם יספרו לך מספר הפעמים (זה בדיוק הסיגמא של הCk), סה"כ מכפלה עם FFT לוקחת Onlogn, מעבר על Ck זה O2n, וסה"כ Onlogn. לגבי 1. את ההצבה אתה צריך לעשות חכם בשביל להמנע מהעלות בחזקה כפולות => כלל הורנר אם אתה מכיר מאנליזה נומרית. ובכל אופן, השיטה שלך נראית לי בסדר (רק תוודא את הסיבוכיות של החלוקת פולינומים שלך), אם היה כאן שימוש בFFT היה חייב להיות nlogn איפשהו (זה פשוט המחיר של מעבר בין המרחבים), לפי דעתי, זה בעיקר בשביל להראות את כלל הורנר.

 

[1ca1]

אופס

כמובן מעבר על Ck בין 0 ל30n

 

[yythe1]

לומד בבר אילן

תודה . יש כאן משהו שלא הבנתי כל כך . הדרגה היא n^15? זאת דרגה עצבנית ביותר... אין סיכוי שאעבור עליה בn logn

 

[1ca1]

הפוך, הדרגה היא 15n...

 

[yythe1]

אה , דרגה של 15n... נכון?

 

[yythe1]

הבנתי , תודה ענקית ענקית ובוקר טוב : )

 

[JohnnyPiloni]

יש לך אישור ל 1

אם תציב את x0 בפולינום תקבל את A(x והוא שווה לr