רוטר - מה סיבוכיות הזמן והמקום של התרגיל הבא?

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

"מה סיבוכיות הזמן והמקום של התרגיל הבא?"

גירסת הדפסה

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

אשכול מספר 14284

idan192

21:02 02.09.07

מה סיבוכיות הזמן והמקום של התרגיל הבא?

אני רוצה להיות בטוח שאני מבין את הנושא.
אשמח אם גם תצרפו פירוט.

שתף

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

האשכול	מחבר	תאריך כתיבה	מספר
O(משהו) :\|	DLN	02.09.07 22:26	1
אם כבר טטא משהו \|: יש למישהו תשובה?	idan192	02.09.07 23:09	2
ICQ, תתחבר אעזור לך כמה שאוכל.	FireAngel	03.09.07 21:35	3
ממבט לא מעמיק...	Snaker	03.09.07 22:22	4
כן, יצא לי זמן גם כן ON^2 נדמה לי, ומקום?	idan192	03.09.07 22:26	5
סיבוכיות המקום היא כמה מקום אתה מקצה לביצוע	Snaker	03.09.07 22:41	6
כלומר שתיים בחזקת n?	idan192	03.09.07 23:25	7
2 בחזקת n/2...	Snaker	04.09.07 00:15	8
בסדר... אבל כשזה טטא השורש שתיים מצטמצם	idan192	04.09.07 11:43	9
לא... יש הבדל אסימפטוטי בין	Snaker	04.09.07 14:38	10

DLN
חבר מתאריך 20.4.07
15884 הודעות

22:26 02.09.07

1. O(משהו) :|
בתגובה להודעה מספר 0

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

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

idan192

23:09 02.09.07

2. אם כבר טטא משהו |: יש למישהו תשובה?
בתגובה להודעה מספר 1

ערכתי לאחרונה בתאריך 03.09.07 בשעה 17:42 בברכה, idan192

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

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

FireAngel

21:35 03.09.07

3. ICQ, תתחבר אעזור לך כמה שאוכל.
בתגובה להודעה מספר 0

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

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

Snaker

22:22 03.09.07

4. ממבט לא מעמיק...
בתגובה להודעה מספר 0

כל פעם שיש n זוגי זה מתפצל ל-2 פונקציות זהות.
כל פעם שיש n זוגי זה ממשיך עם פונקציוה אחת.

כלומר בסך הכל יש לך 2^(n/2) פיצולים, וזוהי גם סיבוכיות הזמן והמקום, כלומר O(2^n).

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

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

idan192

22:26 03.09.07

5. כן, יצא לי זמן גם כן ON^2 נדמה לי, ומקום?
בתגובה להודעה מספר 4

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

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

Snaker

22:41 03.09.07

6. סיבוכיות המקום היא כמה מקום אתה מקצה לביצוע
בתגובה להודעה מספר 5

ערכתי לאחרונה בתאריך 03.09.07 בשעה 22:55 בברכה, Snaker

התוכנית.
ויש שתי אפשרויות לתוכנית לתפוס את המקום הזה.
להקצות זיכרון (דינאמי) שהוא תלוי בגודל הקלט, למשל הקצאה של מערך בגודל N.
להקצות מקום בזיכרון במחסנית הקריאות (כל קריאה לפונקציה שתופסת מקום), שוב בצורה שהיא תלויה בגודל הקלט (וזה מה שקורה בתוכנית הזו).

עכשיו מקום של כל זימון הוא O(1) ולעבור על כל פונקציה(מבלי לעבור לפ' שהיא קוראת להן) זה גם כן O(1), כל זה קורה 2 בחזקת n/2 פעמים, ולכן במקרה הזה זה שווה.

תיקון: 2 בחזקת n/2 נשאר ככה. ולא הופך ל 2 בחזקת n.
ולכן סיבוכיות המקום והזמן היא 2 בחזקת n/2 .

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

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

idan192

23:25 03.09.07

7. כלומר שתיים בחזקת n?
בתגובה להודעה מספר 6

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

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

Snaker

00:15 04.09.07

8. 2 בחזקת n/2...
בתגובה להודעה מספר 7

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

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

idan192

11:43 04.09.07

9. בסדר... אבל כשזה טטא השורש שתיים מצטמצם
בתגובה להודעה מספר 8

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

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

Snaker

14:38 04.09.07

10. לא... יש הבדל אסימפטוטי בין
בתגובה להודעה מספר 9

שורש 2 בחזקת n
ל-2 בחזקת n.

2 בחזקת n "צומח" הרבה יותר מהר...

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

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