שבוע 1-3 Flashcards
(23 cards)
כמה מקום תופס bubble sort?
n כי עובדים על אותו מערך
מה זמן הריצה הטוב ביותר של bubble sort?
n כי עובר על כל המערך ולא מחליף כלום
איך מסומן חסם עליון
O גדול
f(n) =O (g(n)) כלומר:
קיים סי גדול מאפס ואן טבעי כך שלכל טבעי גדול מאן מתקיים:
f(n) <= c*g(n)
כלומר
g הוא חסם עליון
עבור f
איך מסומן חסם תחתון?
Big Omega Notation
f(n) = BIG OMEGA(g(n)) כלומר:
קיים סי גדול מאפס וקיים אן גדול מאפס כך שלכל טבעי גדול מאן מתקיים:
f(n) >= c*g(n)
כלומר g הוא חסם תחתון
עבור f
איך מסמנים חסם הדוק?
Theta העיגול עם השטות בפנים
מה זה אומר שיש חסם הדוק
f(n) = O (g(n))
וגם
f(n) = BIG OMEGA (g(n))
מה זה שמורת לולאה?
מה זה חסם עליון ממש?
זה אומר ש אף ממש זניחה ביחס ל גי כי לכל סי חיובי
f(n)< c*g(n)
מה זה חסם תחתון ממש?
אומגה קטן נראה כמו w
זה אומר ש גי זניחה ביחס לאף
log_b(m) + log_b(n) =
log_b (m*n)
a^x =b. x =?
log _a (b)
לוג איי של בי
לוג בי של אמ פחות לוג בי של אן זה
לוג בי של אמ חלקי אן
log_b(a) * log_a(n) =
log_b(n)
b^(log_b(n)) =
n
for all b, log_b(n) = ?
Tetha log n
for all e>0, log n =?
o (n^e)
𝑇(𝑛) = 𝑎 𝑇(𝑛 𝑏⁄ ) + Θ(𝑛^k) ?
נוסחת זמן של אלגוריתם רקורסיבי?
אם
a / b^k < 1
אז
T(n) = Theta (n^k)
אם
a / b^k = 1
אז
T(n) = Theta (log n * n^k)
אם
a / b^k > 1
אז
T(n) = Theta (n^(log_b(a)))
