רוטר - צריך עזרה בחישוב סיבוכיות אלגוריתם:

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

"צריך עזרה בחישוב סיבוכיות אלגוריתם:"

גירסת הדפסה

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

אשכול מספר 10047

Zvikadori
חבר מתאריך 3.8.02
5369 הודעות, דרג אמינות חבר זה

23:33 14.03.10

צריך עזרה בחישוב סיבוכיות אלגוריתם:

האלגוריתם ממש לא מסובך, אבל די נתקעתי:

for int i=n i>=1 i--
{
x=1
while x<i
x=x*2
while x>2
x=sqrt(x)
}
סה"כ ברור לי כי האלגוריתם רץ n פעמים על הלולאת ה-for.
הוא רץ במקרה הרע logn פעמים על לולאת ה-while הראשונה.
אבל מה הולך עם הלולאה ה-2? איזה חישוב עליי לעשות?
האם זה נכון שבמקרה הרע:
x=2^i צריך להיות קטן מ-2 אחרי k איטרציות? איך לחשב את k?

בתודה מראה

שתף

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

האשכול	מחבר	תאריך כתיבה	מספר
מכתב	Deuce	15.03.10 03:12	1
אחי, קצת הסתבכתי עם מה שאמרת...	Zvikadori	15.03.10 18:59	2
בעצם נראה לי שעכשיו הבנתי...	Zvikadori	15.03.10 20:06	4
אממ אם לא ניתחתי את זה באופן רשלני מידי בראש זה נראה לי טטא של N	ronen333	15.03.10 19:40	3
nlogn...	Zvikadori	15.03.10 20:18	5
ה2 נבלעת בראשונה.	ronen333	16.03.10 15:53	12
קבל:	ldan192	15.03.10 21:34	6
ה-2 מבחינתי הייתה ה-while ה-1...אולי לא לאורך כל האשכול	Zvikadori	16.03.10 01:18	9
קצת מפורט יותר.	Deuce	15.03.10 23:49	7
המצד שני קצת יותר רגיש ממה שרשמת. הוא נובע כי:	ldan192	16.03.10 00:14	8
אגב, את האי שיוויונות הללו הראו לנו בתרגול,	Zvikadori	16.03.10 02:16	10
אחרי חודש כבר זה יהיה לך אינטואיטיבי.	Deuce	16.03.10 11:38	11

Deuce
חבר מתאריך 1.9.08
6225 הודעות, דרג אמינות חבר זה

03:12 15.03.10

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

אתה אומר כי x = 2^k לאחר k איטרציות. מכאן אתה פותר 2 ב-k קטן מ-i אמם k > log i עד כדי עיגול עליון. ואז את המסיק את המסקנה.

בכל מקרה, שים לב לשורש(X) - כמה זה עולה לך.

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

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

Zvikadori
חבר מתאריך 3.8.02
5369 הודעות, דרג אמינות חבר זה

18:59 15.03.10

2. אחי, קצת הסתבכתי עם מה שאמרת...
בתגובה להודעה מספר 1

נאמר שהלולאת ה-while הראשונה רצה עד ש-

2^i<n

כלומר, i=lgn
ואז קיבלתי ש-x= 2^i
וכעת עליי להיכנס לתוך הלולאה ה-2 שרצה עד ש-x<2 לכן:

2^(i/2k)=2
where i=lgn
therefore
lgn/2k=1
k=lg(sqrt(n))
הרי ברור שלולאת ה-while דורשת יותר זמן(כי קצב הגידול של X שונה בהרבה בין הלולאה הראשונה ל-2).
האם מה שאני אומר פה נכון(בעיקר לגבי הלולאה ה-2)...
כלומר יש לנו O(n^3/2)-(זאת המסקנה שהתכוונת?)

תודה רבה אחי!!

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

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

Zvikadori
חבר מתאריך 3.8.02
5369 הודעות, דרג אמינות חבר זה

20:06 15.03.10

4. בעצם נראה לי שעכשיו הבנתי...
בתגובה להודעה מספר 2

בגלל ש-x=2*x הבנתי ש-
i=2^k
ז"א k=lg(i)
כאשר k=מס' האיטרציות ללואת ה-while ה-1...
כאשר נגיע כבר ללולאה ה-2 i יהיה קטן או שווה ל-X
בהנחה שהוא יהיה x ובהנחה כי הפעולה בתוך ה-while ה-2 היא x=sqrt(x)
אז בעצם נקבל:

i^1/(2^m)
וזה צריך להיות שווה ל-2(או קטן ממנו על מנת להפעיל את תנאי העצירה).

ועכשיו הכל מסתדר לי...

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

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

ronen333
חבר מתאריך 20.2.03
6069 הודעות, דרג אמינות חבר זה

19:40 15.03.10

3. אממ אם לא ניתחתי את זה באופן רשלני מידי בראש זה נראה לי טטא של N
בתגובה להודעה מספר 0

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

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

Zvikadori
חבר מתאריך 3.8.02
5369 הודעות, דרג אמינות חבר זה

20:18 15.03.10

5. nlogn...
בתגובה להודעה מספר 3

בגלל הלולאה ה-2...שהיא הדומיננטית...

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

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

ronen333
חבר מתאריך 20.2.03
6069 הודעות, דרג אמינות חבר זה

15:53 16.03.10

12. ה2 נבלעת בראשונה.
בתגובה להודעה מספר 5

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

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

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

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

21:34 15.03.10

6. קבל:
בתגובה להודעה מספר 0

ערכתי לאחרונה בתאריך 15.03.10 בשעה 22:03 בברכה, ldan192

קודם כל, הלולאה הכללית היא כזו:
(T(n)=T(n-1)+O(logn)+G(n
כאשר G(n)=G(sqrt(n))+1
תיקח m=logn, אזי
G(2^m)=G(2^(m/2))+1
תציב (S(m)=G(2^m
S(m)=S(m/2)+1
לפי כל משפט שתרצה
G(n)=loglogn
כעת, שניה אני רואה שהטקסט התבלגן,
הינה:
(T(n)=T(n-1)+O(logn)+O(loglogn)=T(n-1)+O(logn)=...=T(1)+sum from 1 to n log i <= O(nlogn

אז כפי שאתה רואה, דווקא הלולאה ראשונה היא הדומיננטית ואל השניה.

בברכה,
עידן

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

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

Zvikadori
חבר מתאריך 3.8.02
5369 הודעות, דרג אמינות חבר זה

01:18 16.03.10

9. ה-2 מבחינתי הייתה ה-while ה-1...אולי לא לאורך כל האשכול
בתגובה להודעה מספר 6

אבל בהודעה האחרונה כן...
ואם כך אז פתרתי נכון(לבסוף...)

יצא לי בדיוק כמו שעשית

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

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

Deuce
חבר מתאריך 1.9.08
6225 הודעות, דרג אמינות חבר זה

23:49 15.03.10

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

לא נכנסתי כל כך לתשובות שלכם, בגלל מחסור בזמן - אבל אני אתן לך בכללי את התשובה שתוכל לוודא, בהנחה שאני בעצמי לא עושה בלבול.
לולאה פנימית אחת בהנתן i רצה log i פעמים.
אח"כ יש לולאה פנימית שלוקחת את x = i (בערך) ומוציאה ממנו שורש שוב ושוב עד שהוא גדול מ-2. כמה פעמים צריך להוציא ל-i שורש עד שהוא מגיע ל-2? אתה יודע שפחות פעמים מכמות הפעמים שלוקח לחלק אותו בשתיים עד שהוא מגיע ל-2 כי שורש(X) קטן מ-X/2 (זה נכון החל מ-4 לפחות), ז"א שסה"כ זה יהיה פחות מלוג i פעולות. עם זאת יש הנחה סמוייה כנראה שהוצאת השורש היא פעולה של O(1) - זה לא ככה במציאות.
לסיכום סיבוכיות:
מצד אחד,

Sigma(log i) <= nlog n
i = 1 to n
מצד שני,

Sigma(log i) >= (n/2)*log (n/2)

ולכן הסיבוכיות המבוקשת היא nlog n.

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

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

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

00:14 16.03.10

8. המצד שני קצת יותר רגיש ממה שרשמת. הוא נובע כי:
בתגובה להודעה מספר 7

Sigma (logi) >= Sigma(logi) >= Sigma(log(n/2)) >= (n/2)*log(n/2)
i=1 to n i=n/2 to n i=n/2 to n

אבל כמובן שאתה צודק, רק שאני קיבלתי את הרושם שהוא דיבר על חסם עליון ולא הדוק.

בברכה,
עידן

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

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

Zvikadori
חבר מתאריך 3.8.02
5369 הודעות, דרג אמינות חבר זה

02:16 16.03.10

10. אגב, את האי שיוויונות הללו הראו לנו בתרגול,
בתגובה להודעה מספר 8

הקטע שהם לא אינטואיטביים... אבל אם מישהו מוביל אותך אליהם או שאתה רואה את זה פעם אחת זה נחרט...

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

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

Deuce
חבר מתאריך 1.9.08
6225 הודעות, דרג אמינות חבר זה

11:38 16.03.10

11. אחרי חודש כבר זה יהיה לך אינטואיטיבי.
בתגובה להודעה מספר 10

אתה יודע בלב שזאת הסיבוכיות ורק צריך לעשות את זה פורמלי.
למה n/2log n/2 כי log n/2 זה בערך האיבר האמצעי והוא קטן שווה מכל האיברים הבאים אחריו, לכן n/2log n/2.

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

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