שאלת מבחן באלגוריתמים - האוניברסיטה הפתוחה 2021 - התמרת פורייה מהירה

נתונות שתי קבוצות של מספרים טבעיים $S,T\subseteq\{1,\dots,n\}$ שגודלן $|S|,|T|=\Theta(n)$. סכומן של הקבוצות מוגדר $S+T=\{z\mid \exists x\in S,\ \exists y\in T\ \text{s.t.}\ x+y=z\}$ (למשל $S=\{1,4\},T=\{7,10,40\}$ נותנות $S+T=\{8,11,14,41,44\}$). הציגו אלגוריתם לחישוב $S+T$ בזמן $\Theta(n\log n)$ (פעולות אריתמטיות בסיסיות). הדרכה: היעזרו ב-FFT.

רמז: ייצגו כל קבוצה כפולינום שחזקותיו הן איברי הקבוצה. מהי המשמעות של מכפלת שני הפולינומים (קונבולוציה) מבחינת החזקות, וכיצד היא מחשבת את $S+T$?

פתרון: **האלגוריתם.** 0. הגדר פולינומים $p(x)=\sum_{i\in S} x^i$ ו-$q(x)=\sum_{j\in T} x^j$ (מקדם 1 בחזקות ששייכות לקבוצה). 1. חשב את הקונבולוציה $h(x)=p(x)\cdot q(x)$ באמצעות FFT. 2. החזר את קבוצת החזקות שמקדמן ב-$h(x)$ **אינו אפס** — זו הקבוצה $S+T$. **נכונות.** $x^i\cdot x^j=x^{i+j}$, ולכן החזקות בעלות מקדם חיובי ב-$h(x)$ הן בדיוק $\{i+j\mid i\in S,\,j\in T\}=S+T$ (המקדם של $x^k$ סופר את מספר הזוגות $(i,j)$ עם $i+j=k$, והוא חיובי אמ"מ $k\in S+T$). **זמן ריצה.** $\deg h\le 2n$, ולכן FFT מסדר החזקה של 2 הקרובה ל-$2n$: כפל שתי התמרות + iFFT בזמן $\Theta(n\log n)$. $\blacksquare$