הבדלים בין גרסאות בדף "קוד:סימני לנדאו"

גרסה אחרונה מ־20:16, 4 באוקטובר 2014

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

\begin{enumerate} \item מסמנים $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 $ .

\item מסמנים $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$ משום שאלה סדרות, אבל בפונקציות זה גם יתקיים סביב נקודות)

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

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