| כותב |
|
יניב
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 14 February 2007 בשעה 21:06 | | IP רשוּם
|
|
|
|
אני די בטוח שזה שייך לפה..בכל זאת זה שאלה ממבחן למבוא למדעי המחשב :
http://img440.imageshack.us/my.php?image=untitledkz3.jpg
תודה
|
| חזרה לתחילת העמוד |
|
| |
יניב
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 14 February 2007 בשעה 21:10 | | IP רשוּם
|
|
|
|
ועוד שאלה אם מותר לי..בפסקאל
http://img253.imageshack.us/img253/6779/untitledmy3.jpg
היעילות של MERGE SORT כאמור היא nlogn אבל לאחר מכן מתבצעות עוד פעולות בתת תוכנית וישנה עוד לולאה.אז איך יוצא שבתשובה לתרגיל היעילות היא nlogn ,האם לא מתחשבים בלולאה הנוספת?
|
| חזרה לתחילת העמוד |
|
| |
pitbull
משתמש חבר
הצטרף / הצטרפה: 14 May 2005
משתמש: מנותק/ת
הודעות: 209
|
| נשלח בתאריך: 14 February 2007 בשעה 22:17 | | IP רשוּם
|
|
|
|
לגבי השאלה השנייה, זה לא משנה מה קורה בשאר התוכנית, אם יש לולאה שעוברת על המערך ומדפיסה/קולטת את הערכים זה לא משנה כי מה שאתה מחפש בעצם זה היעילות של אלגוריתם merge sort בלבד. וזה בדיוק מה שהבאת בתמונה.
|
| חזרה לתחילת העמוד |
|
| |
יניב
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 15 February 2007 בשעה 09:16 | | IP רשוּם
|
|
|
|
לא מובן לי משו..הרי יש המשך לתוכנית ואפילו עוד לולאה ובדיקות..אז איך לא מחשיבים את זה?
|
| חזרה לתחילת העמוד |
|
| |
Fate
פורומיסט על
הצטרף / הצטרפה: 25 October 2005
משתמש: מנותק/ת
הודעות: 571
|
| נשלח בתאריך: 15 February 2007 בשעה 09:43 | | IP רשוּם
|
|
|
|
מחשיבים את זה.... אבל זה לא משפיע על הסיבוכיות כי זה לא תלוי באורך קלט.
אם יש לך תוכנית שקולטת מערך (לולאה אחת)
עוברת על המערך ומחסרת מכל מספר 2 (לולאה שנייה)
ואז עוברת שוב על המערך ומדפיסה אותו (לולאה שלישית)
הסיבוכיות של כל זה זה N...
בגלל שכמות הפקודות המתבצעות ניתן לחשב ע"י משהו כזה:
(3na + b)
בהנחה וn זה גודל המערך...
וa זה כמות הפקודות בכל לולאה (בהנחה וזה אותה כמות)
וb זה כמות הפקודות מסביב שלא נמצאות באף לולאה.
עכשיו בחישוב סיבוכיות, מחשבים כאשר n שואף לאינסוף...
ז"א 3, a, b, לא באמת משנה....
הסיבוכיות הכי גבוהה אצלך בתוכנית של הmerge היא של האלגוריתם עצמו.
וזה n* logn...
|
| חזרה לתחילת העמוד |
|
| |
יניב
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 15 February 2007 בשעה 09:50 | | IP רשוּם
|
|
|
|
אז למה נגיד בbubble sort הסיבוכיות היא N בריבוע..הרי גם שם יש שתי לולאות...או שזה בגלל שבלולאה השניה מספר הפעולות יכול להשתנות מפעם לפעם ולא קבוע ולכן זה יוצא N בריבוע?
|
| חזרה לתחילת העמוד |
|
| |
Fate
פורומיסט על
הצטרף / הצטרפה: 25 October 2005
משתמש: מנותק/ת
הודעות: 571
|
| נשלח בתאריך: 15 February 2007 בשעה 11:56 | | IP רשוּם
|
|
|
|
בbubble sort אתה צריך לשים לב לכמות הפעולות שמתבצעות...
תשים לב שעל כל איבר נוסף במערך, אנחנו נצטרך לעבור פעם נוספת על כל המערך...
אם יש 10 איברים לסדר, אז נצטרך לרוץ 10 פעמים עם כל המערך של 10.
שזה יוצא 100...
אם ניקח מערך של n אז נצטרך לרוץ על n איברים, n פעמים...
מה שאומר:
n * n * a + b
ובהנחה וn שואף לאינסוף..
יוצא לך n בריבוע...
|
| חזרה לתחילת העמוד |
|
| |
נושאים פעילים
רשימת משתמשים
חיפוש
עזרה
הרשמה
התחברות
UnderWarrior Forums : 
תיכנות
