קוד:סימני לנדאו

סימני לנדאו מהווים דרך קצרה לכתוב מידע על התנהגות פונקציות אחת ביחס לשנייה בסביבת נקודה או "באינסוף". פה נמצאים ההגדרות של הסימנים עבור סדרות, עבור פונקציות ניתן להגדיר בצורה אנלוגית. $\\$ תהיינה הסדרות $\{a_n\}_{n=1}^\infty , \{b_n\}_{n=1}^\infty $

1. מסמנים $a_n=O(b_n) , n\to \infty $ ("הסדרה $a_n$ היא O גדול של $b_n$") אם מתקיים $\exists_{M>0} \exists_{n_0} \forall_{n>n_0} 0\leq a_n \leq M\cdot b_n $ . הסימן הזה חוזר המון במחשבים כשבודקים יעילות של אלגוריתמים. לדוגמה אלגוריתם שמקבל קלט $n$ מסוים ועושה $a_n=2n+4 $ פעולות אומרים שהיעילות שלו היא מסדר $O(n)$ משום שאכן $ 2n+4=O(n) , n\to \infty $ , כי אם ניקח $M=3 $ אז אכן ממקום מסוים והלאה, $2n+4\leq 3n $ .

2. מסמנים $a_n=O^* (b_n) , n\to \infty $ אם מתקיים $\exists_{M,m>0} \exists_{n_0} \forall_{n>n_0} m_0\cdot b_n\leq a_n \leq M\cdot b_n $ . שימו לב שאם $a_n=O^* (b_n) $ אז $a_n=O(b_n) $ וגם $b_n=O^* (a_n) $ (כל אלה כמובן כש- $n\to \infty$ משום שאלה סדרות, אבל בפונקציות זה גם יתקיים סביב נקודות)

3. נניח $b_n\neq 0 $ אז אפשר להגדיר את הסימן $a_n=o(b_n) $ ("O קטן") אם $\lim_{n\to \infty} \frac{a_n}{b_n} = 0 $ . אפשר לחשוב על זה אינטואיטיבית של $b_n$ גדל הרבה הרבה יותר מהר מ-$a_n$ או ש- $a_n$ אפסי לעומת $b_n$, הסימן הזה יחזור הרבה כשנדבר על נגזרות. דוגמה: $\frac{1}{n^2}=o(\frac{1}{n}),n\to\infty $

4. $ a_n\sim b_n, n\to \infty$ אם ורק אם $\lim_{n\to \infty} \frac{a_n}{b_n} = 1 $