מתוך ויקיספר, אוסף הספרים והמדריכים החופשי
דף זה מכיל מספר סימונים ונוסחאות שימושיים לקורס.
דוגמה:
⌈
2.5
⌉
=
3
{\displaystyle \displaystyle \left\lceil 2.5\right\rceil =3}
⌊
2.5
⌋
=
2
{\displaystyle \displaystyle \left\lfloor 2.5\right\rfloor =2}
[ עריכה ]
הגדרה:
בקורס זה, בסיס הלוגריתם הוא 2, אא"כ צויין אחרת: לכל
a
>
0
{\displaystyle \displaystyle a>0}
log
(
a
)
=
log
2
(
a
)
{\displaystyle \displaystyle \log(a)=\log _{2}(a)}
משפט:
לכל
a
,
b
,
c
>
0
{\displaystyle \displaystyle a,b,c>0}
a
log
b
(
c
)
=
c
log
b
(
a
)
{\displaystyle \displaystyle a^{\log _{b}(c)}=c^{\log _{b}(a)}}
a
=
2
log
(
a
)
{\displaystyle \displaystyle a=2^{\log(a)}}
משפט: נוסחת סטירלינג
2
π
n
(
n
e
)
n
≤
n
!
≤
2
π
n
(
n
e
)
n
+
1
12
n
{\displaystyle \displaystyle {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n}\leq n!\leq {\sqrt {2\pi n}}\left({\frac {n}{e}}\right)^{n+{\frac {1}{12n}}}}
כדאי לדעת:
מותר להשתמש בנוסחת סטירלינג גם ללא ידיעת הוכחתה.
פעמים רבות, במהלך ניתוח סדר הגדילה של אלגוריתם כלשהו, יש לנתח את סדר הגדילה של טור כלשהו. נראה כעת מספר טורים שימושיים שיופיעו רבות במהלך החומר, וטכניקה כללית לניתוח טורים רבים.
הוכחה: (4)
מצד אחד,
∑
i
=
1
n
[
log
(
i
)
]
≤
∑
i
=
1
n
[
log
(
n
)
]
=
n
⋅
log
(
i
)
{\displaystyle \displaystyle \sum _{i=1}^{n}[\log(i)]\leq \sum _{i=1}^{n}[\log(n)]=n\cdot \log(i)}
ולכן
∑
i
=
1
n
[
log
(
i
)
]
=
O
(
n
⋅
log
(
n
)
)
{\displaystyle \displaystyle \sum _{i=1}^{n}[\log(i)]=O(n\cdot \log(n))}
∑
i
=
1
n
[
log
(
i
)
]
≥
∑
i
=
⌈
n
/
2
⌉
n
[
log
(
i
)
]
≥
∑
i
=
⌈
n
/
2
⌉
n
[
log
(
⌊
n
/
2
⌋
)
]
≥
(
n
/
2
−
1
)
⋅
log
(
n
/
2
−
1
)
{\displaystyle \displaystyle \sum _{i=1}^{n}[\log(i)]\geq \sum _{i=\left\lceil n/2\right\rceil }^{n}[\log(i)]\geq \sum _{i=\left\lceil n/2\right\rceil }^{n}[\log(\left\lfloor n/2\right\rfloor )]\geq (n/2-1)\cdot \log(n/2-1)}
ולכן
∑
i
=
1
n
[
log
(
i
)
]
=
Ω
(
n
⋅
log
(
n
)
)
{\displaystyle \displaystyle \sum _{i=1}^{n}[\log(i)]=\Omega (n\cdot \log(n))}
מבחן גבול מנות ).
[ עריכה ] בקורס זה אנו מניחים ידע בסיסי בתורת הקבוצות . להלן מספר סימונים:
סימון קבוצה על ידי איבריה:
A
=
{
a
1
,
…
,
a
n
}
{\displaystyle \displaystyle A=\left\{a_{1},\ldots ,a_{n}\right\}}
שיוך איבר
a
{\displaystyle \displaystyle a}
A
{\displaystyle \displaystyle A}
a
∈
A
{\displaystyle \displaystyle a\in A}
הכלת קבוצה
B
{\displaystyle \displaystyle B}
A
{\displaystyle \displaystyle A}
B
⊆
A
{\displaystyle \displaystyle B\subseteq A}
גודל קבוצה
A
{\displaystyle \displaystyle A}
|
A
|
{\displaystyle \displaystyle \vert A\vert }
הפרש בין קבוצות
A
{\displaystyle \displaystyle A}
B
{\displaystyle \displaystyle B}
A
{\displaystyle \displaystyle A}
B
{\displaystyle \displaystyle B}
A
∖
B
{\displaystyle \displaystyle A\setminus B}
![{\displaystyle \displaystyle \sum _{i=1}^{n}[i]={\frac {n\cdot (n+1)}{2}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/be335c489127906b00ec0532c05f8279faccd157)
![{\displaystyle \displaystyle \forall _{q\neq 1}\sum _{i=1}^{n}[q^{i}]={\frac {q^{n+1}-1}{q-1}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/05c29f320c9ad43fe4312d5fa2444c64eff39952)
![{\displaystyle \displaystyle \forall _{0<q<1}\sum _{i=1}^{\infty }[q^{i}]={\frac {1}{1-q}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f37ae3ad60372f3328d466780b1c9df015d7436b)
![{\displaystyle \displaystyle \sum _{i=1}^{n}[\log(i)]=\Theta (n\cdot \log(n))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0f116613809a87640ad4c06e60144f9545fa8ad6)
![{\displaystyle \displaystyle \sum _{i=1}^{n}[\log(i)]\leq \sum _{i=1}^{n}[\log(n)]=n\cdot \log(i)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b6f0a3964e9a16165e07e626fa89b3c20b927109)
![{\displaystyle \displaystyle \sum _{i=1}^{n}[\log(i)]=O(n\cdot \log(n))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/70a3ddac2af677547eda999b40cf72899f7fc743)
![{\displaystyle \displaystyle \sum _{i=1}^{n}[\log(i)]\geq \sum _{i=\left\lceil n/2\right\rceil }^{n}[\log(i)]\geq \sum _{i=\left\lceil n/2\right\rceil }^{n}[\log(\left\lfloor n/2\right\rfloor )]\geq (n/2-1)\cdot \log(n/2-1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cab1e8de1bee90554b9fca33bb1c806d9af4688b)
![{\displaystyle \displaystyle \sum _{i=1}^{n}[\log(i)]=\Omega (n\cdot \log(n))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8d6a20d07d22fbb08f4d4e8f2537e0975d9087dd)
![{\displaystyle \displaystyle \int _{m-1}^{n}f(x)dx\leq \sum _{i=m}^{n}[f(i)]\leq \int _{m}^{n+1}f(x)dx}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e904a3978702831a002b072b8c21e07caa6717db)
![{\displaystyle \displaystyle \int _{m}^{n+1}f(x)dx\leq \sum _{i=m}^{n}[f(i)]\leq \int _{m-1}^{n}f(x)dx}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7aa781e7f8a129153032b83188b464a60655dfad)
