רוטר - עזרה במציאת נוסחה סגורה עבור נוסחאת נסיגה

יומן פעילות	לוח שנה	מבזקי חדשות	תקנון	RSS	כותרות	כותרות לפי תגובה	ניקוי קוקיז	IP	להורדת אפליקציה
eBay	AliExpress	GearBest	Amazon	Booking	Kiwi	SkyScanner	Trip Advisor

"עזרה במציאת נוסחה סגורה עבור נוסחאת נסיגה"

גירסת הדפסה

קבוצות דיון לימודים, מדע ותרבות נושא #21037	מנהל סגן המנהל מפקח Winner צל"ש מומחה

אשכול מספר 21037

Adielb

חבר מתאריך 22.6.11
7352 הודעות, 7 פידבק

23:55 28.11.14

עזרה במציאת נוסחה סגורה עבור נוסחאת נסיגה

T(n,k) = T(n^1/2) +k
כאשר k *אינו* קבוע
אני מניח שזה די דבילי, אבל לא בטוח כיצד לגשת לזה?
האם להשתמש בשיטת הניחוש ולומר שזה O(n^1/2+k) ?
אם אני הולך לפי זה יוצא לי שהקבוע שלי צריך להיות לפחות 1
אבל אני לא בטוח אם ככה עושים במקרה כזה
או שבכלל צריך ללכת על הצבה?
m = logn
n = 2^m
T(n,k) = T(2^m,k) = T(2^m/2)+k
לסמן:
S(y,k) = T(2^y,k)
S(m,k) = T(2^m,k) = S(m/2)+k
ואז ידוע ש:
S(m,k) = Teta(k*logm)
ואז מתקבל:
T(n,k) = T(2^m,k) = S(m,k) = Teta(k*log(logn))
???
באמת שאני לא מבין מה עושים פה למרות שזה בטח פשוט

אשמח לעזרה

שתף

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

האשכול	מחבר	תאריך כתיבה	מספר
הסתדרתי (פתיחת הרקורסיה והגדרת תנאי עצירה נוסף)	Adielb	30.11.14 13:57	1
כאילו בדקת מה מספר הצעדים כדי ששורש N שווה לאחד ואז הכפלת את הסכום הזה ב-K?	Dark-Wish	30.11.14 22:10	2
מכתב	Adielb	30.11.14 23:30	3
תודה :)	Dark-Wish	01.12.14 00:15	4

Adielb

חבר מתאריך 22.6.11
7352 הודעות, 7 פידבק

13:57 30.11.14

1. הסתדרתי (פתיחת הרקורסיה והגדרת תנאי עצירה נוסף)
בתגובה להודעה מספר 0

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Dark-Wish
חבר מתאריך 25.5.05
12576 הודעות

22:10 30.11.14

2. כאילו בדקת מה מספר הצעדים כדי ששורש N שווה לאחד ואז הכפלת את הסכום הזה ב-K?
בתגובה להודעה מספר 1

(וגם חישבת את הסכום)

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Adielb

חבר מתאריך 22.6.11
7352 הודעות, 7 פידבק

23:30 30.11.14

3. מכתב
בתגובה להודעה מספר 2

T(n,k) = T(n^0.5) + k = T(n^0.25) + 2k = ....
= T( n^((0.5)^i)) ) + i*k

ואז צריך להגדיר תנאי עצירה של n=2 כי עבור n=1 מקבלים:

n^((0.5)^i = 1
log(n) = log(1)*2^i
log(n) = 0*2^i
אז פשוט קבעתי שהקלט יעצור כאשר ה- n בחזקת כל הקשקוש שווה ל2,
שמה מקבלים ש- i = log(logn)
וקבעתי ש-T(2) שווה ל-1 (אמרו שמותר לנו להוסיף תנאי עצירה אם נדרש)

ואז זה יוצא
O(1) + O(k*log(logn)
שזה O(k*log(logn)

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד

Dark-Wish
חבר מתאריך 25.5.05
12576 הודעות

00:15 01.12.14

4. תודה :)
בתגובה להודעה מספר 3

(ניהול: מחק תגובה)

מכתב זה והנלווה אליו, על אחריות ועל דעת הכותב בלבד