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

מתוך Math-Wiki
קפיצה אל: ניווט, חיפוש
(יצירת דף עם התוכן "סימני לנדאו מהווים דרך קצרה לכתוב מידע על התנהגות פונקציות אחת ביחס לשנייה בסביבת נקודה...")
 
שורה 3: שורה 3:
 
תהיינה הסדרות $\{a_n\}_{n=1}^\infty , \{b_n\}_{n=1}^\infty $
 
תהיינה הסדרות $\{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 $ .  
+
\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 $ .  
  
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$ משום שאלה סדרות, אבל בפונקציות זה גם יתקיים סביב נקודות)
+
\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$ משום שאלה סדרות, אבל בפונקציות זה גם יתקיים סביב נקודות)
  
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 $
+
\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}
  
4. $ a_n\sim b_n, n\to \infty$ אם ורק אם $\lim_{n\to \infty} \frac{a_n}{b_n} = 1 $
+
\item $ a_n\sim b_n, n\to \infty$ אם ורק אם $\lim_{n\to \infty} \frac{a_n}{b_n} = 1 $
 +
\end{enumerate}

גרסה מ־11:20, 3 בספטמבר 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}