רוטר - איך אני מחשב את זמן הריצה הבא?

האשכול	מחבר	תאריך כתיבה	מספר
אולי הניסוח הזה יהיה יותר ברור:	ldan192	05.03.11 12:47	1
למדנו רקורסיה מסטר הצבה ועצים	Yariv-H	05.03.11 13:10	2
כי לא רשמתי את התשובה המלאה. תראה את התגובה לאחר	ldan192	05.03.11 13:26	3
מכתב	Deuce	05.03.11 18:05	4
תודה לשניכם	Yariv-H	05.03.11 19:40	5
ידוע לכם אם קיים מחשבון ברשת שיודע לחשב זמני ריצה?	Yariv-H	05.03.11 19:50	6

ldan192
חבר מתאריך 14.9.08
95853 הודעות

12:47 05.03.11

1. אולי הניסוח הזה יהיה יותר ברור:
בתגובה להודעה מספר 0

ערכתי לאחרונה בתאריך 05.03.11 בשעה 13:26 בברכה, ldan192

T(n) = T(n^0.5) + 1
m=log2(n)
T(2^m) = T(2^(m/2)) + 1
S(m) = T(2^m)
S(m) = S(m/2) +1
S(m) = O(logm)
T(n) = T(2^m) = S(m) = O(logm) = O(loglogn)

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

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

Yariv-H

חבר מתאריך 24.3.02
5879 הודעות, 1 פידבק

13:10 05.03.11

2. למדנו רקורסיה מסטר הצבה ועצים
בתגובה להודעה מספר 1

אחרי שירדתה בכול החזקות למה הסכום של כול ה 1-ים זה log(n)?
log(n) זה לא כאשר אתה מחלק את הקבוצה שלך כול פעם לשתים?

תודה.

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

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

ldan192
חבר מתאריך 14.9.08
95853 הודעות

13:26 05.03.11

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

עריכה, מקווה שיהיה יותר ברור.

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

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

Deuce
חבר מתאריך 1.9.08
6225 הודעות

18:05 05.03.11

4. מכתב
בתגובה להודעה מספר 0

T(n) = T(n^1/2) + 1
T(n^1/2) = T(n^1/4) + 1
...

יש לך את הפונקציה:

f(n) = Sqrt(n)

מספיק לבדוק תוך כמה צעדים הפונקציה מתייצבת על 1, לשם כך נציב:
n = 2^k (עד כדי חסמים k, k+1).
f(n) = Sqrt(2^k) = 2^(k/2)

כלומר אחרי log k צעדים f(n) = 1.
log k = log log n.
ובסה"כ:
T(n) = log log n

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

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

Yariv-H

חבר מתאריך 24.3.02
5879 הודעות, 1 פידבק

19:40 05.03.11

5. תודה לשניכם
בתגובה להודעה מספר 0

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

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

Yariv-H

חבר מתאריך 24.3.02
5879 הודעות, 1 פידבק

19:50 05.03.11

6. ידוע לכם אם קיים מחשבון ברשת שיודע לחשב זמני ריצה?
בתגובה להודעה מספר 0

לבדוק את הפתרונות שלי?

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

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