קוד:סימני לנדאו - היסטוריית גרסאות

ארז שיינר: 2 גרסאות יובאו

2014-10-04T20:16:44Z

2 גרסאות יובאו

→ הגרסה הקודמת	גרסה מ־20:16, 4 באוקטובר 2014
(אין הבדלים)

Ofekgillon10 ב־11:20, 3 בספטמבר 2014

2014-09-03T11:20:45Z

→ הגרסה הקודמת		גרסה מ־11:20, 3 בספטמבר 2014
שורה 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}

Ofekgillon10: יצירת דף עם התוכן "סימני לנדאו מהווים דרך קצרה לכתוב מידע על התנהגות פונקציות אחת ביחס לשנייה בסביבת נקודה..."

2014-08-16T12:59:57Z

יצירת דף עם התוכן "סימני לנדאו מהווים דרך קצרה לכתוב מידע על התנהגות פונקציות אחת ביחס לשנייה בסביבת נקודה..."

דף חדש

סימני לנדאו מהווים דרך קצרה לכתוב מידע על התנהגות פונקציות אחת ביחס לשנייה בסביבת נקודה או "באינסוף". פה נמצאים ההגדרות של הסימנים עבור סדרות, עבור פונקציות ניתן להגדיר בצורה אנלוגית.
$\\$
תהיינה הסדרות $\{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 $