| כותב |
|
מופ
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 05 January 2007 בשעה 10:48 | | IP רשוּם
|
|
|
|
היי שלום..
בסמסטר א' עכשיו אני לומד פסקל...ובזמן האחרון התכנות צריך להתבסס קודם כל על יעילות..בכל מקרה כשמתכוונים ליעילות למה מתכוונים..למספר הבדיקות +מספר הפעולות? או רק למספר הפעולות?
ואיך אפשר לחשב את זה .אם אפשר בכלל? כלומר אני יודע שהכי יעיל זה n log n אבל איך מחשבים את זה?
תודה
|
| חזרה לתחילת העמוד |
|
| |
צחי@
משתמש חבר
הצטרף / הצטרפה: 02 January 2007
מדינה: Israel
משתמש: מנותק/ת
הודעות: 209
|
| נשלח בתאריך: 05 January 2007 בשעה 11:06 | | IP רשוּם
|
|
|
|
ההתייחסות היא למס' הפעולות שמבצעים, כאשר "פעולה" מוגדרת כסדרה סופית של פעולות בסיסיות. לדוגמא, באלגוריתם מיון, פעולת ההשוואה ופעולת ה-SWAP ביחד נספרות כפעולה אחת, בהינתן שהן מבוצעות ברצף.
אפשר לחשב יעילות על סמך ניתוח האלגוריתם/קוד, אבל לפעמים צריך לזכור שהאלגוריתם יותר יעיל או פחות יעיל בהינתן קלט מסויים, ואז אולי אפשר לדבר על יעילות במקרה הגרוע, שזה אומר- בהינתן כל קלט אפשרי לאלגוריתם, מס' הפעולות המקסימלי שעל האלגוריתם לבצע הוא היעילות במקרה הגרוע. בד"כ מדברים על יעילות תוך שימוש במושג O, כאשר מחפשים חסם מלעיל לזמן הריצה של האלגוריתם. אתה יכול לקרוא קצת על ההגדרה של O אבל לצרכים שלך כרגע אני מאמין שספירת הפעולות שמבוצעות (לפי ההגדרה שלי לעיל) היא מספיקה.
אם תיתן דוגמא לאלגוריתם / פסואדו קוד, אני אוכל לנסות לתת לך דוגמא לניתוח יעילותו.
בהצלחה
__________________
דלתות אדריכלים גגות פוליש
|
| חזרה לתחילת העמוד |
|
| |
מופ
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 05 January 2007 בשעה 14:01 | | IP רשוּם
|
|
|
|
לדוגמא התרגיל שבשאלה 2..איך אני מחשב את היעילות ?
תודה
http://www.sendspace.com/file/majrk8
|
| חזרה לתחילת העמוד |
|
| |
צחי@
משתמש חבר
הצטרף / הצטרפה: 02 January 2007
מדינה: Israel
משתמש: מנותק/ת
הודעות: 209
|
| נשלח בתאריך: 05 January 2007 בשעה 14:19 | | IP רשוּם
|
|
|
|
עבור כל זוג איברים במערך מבוצעות 2 פעולות:
1. בדיקת ערך מוחלט של ההפרש
2. עדכון min במידת הצורך.
2 הפעולות הללו שקולות לפעולה אחת לצרכי יעילות כי הן סופיות, מופיעות ברצף ואינן תלויות ב-n.
עכשיו צריך לראות כמה פעמים הן מבוצעות:
כמו שכבר ציינתי בהתחלה, הפעולות מבוצעות פעם אחת לכל זוג איברים, כלומר כמספר הזוגות השונים במערך. יש n*(n-1)/2 זוגות שונים במערך (n מעל 2 בקומבינטוריקה).
מבחינת סדר גודל (עד כדי כפל או חיבור של קבוע) זה שקול ל-n^2.
__________________
דלתות אדריכלים גגות פוליש
|
| חזרה לתחילת העמוד |
|
| |
מופ
אורח
הצטרף / הצטרפה: 01 October 2003
משתמש: אונליין
הודעות: 12647
|
| נשלח בתאריך: 05 January 2007 בשעה 19:18 | | IP רשוּם
|
|
|
|
רגע רגע ...עם נתוך שהמערך הוא בגודל 1000 סך הכל ..ועל כל שתי מספרים מבוצעות 2 פעולות...אז יוצא 1000 פעולות סך הכל לא?
איך אני מגיע ל N^2 אני פשוט לא מצליח להבין ://
מצטער
|
| חזרה לתחילת העמוד |
|
| |
צחי@
משתמש חבר
הצטרף / הצטרפה: 02 January 2007
מדינה: Israel
משתמש: מנותק/ת
הודעות: 209
|
| נשלח בתאריך: 05 January 2007 בשעה 20:39 | | IP רשוּם
|
|
|
|
הפעולות לא מתבצעות על כל 2 מספרים (500 מתוך 1000)
אלא על כל הזוגות השונים, כלומר 2/(1000*999) זוגות שונים.
אולי הדוגמה הבאה תמחיש את זה:
נתון מערך A בגודל 4,
כמה זוגות שונים של איברים יש ב-A ?
קוד:
(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)
|
|
|
ישנם 6 זוגות שונים.
כמו כן, ציינת שמבוצעות 2 פעולות, אבל 2 הפעולות הללו שקולות לפעולה אחת
כי הן פעולות שלוקח זמן קבוע לבצע את שתיהן והן מבוצעות ברצף.
באופן כללי בשאלה יש לולאה חיצונית שמתבצעת n פעמים ובתוכה לולאה פנימית שמתבצעת במקרה הגרוע n פעמים. זה אמור לתת מושג על סדר גודל, שהוא לפחות חסום מלמעלה על ידי n^2 פעולות. במקרה הזה, אפשר להוכיח שגם חסום מלמטה (ראה בהמשך).
אם יש n מספרים אז יש סדר גודל של n^2 זוגות שונים.
נניח ש-f(n) היא פונקציה שנותנת את מספר הזוגות השונים בתלות ב-n.
אם נבחן את ההתנהגות של הפונקציה הזאת אזי, קצב הגדילה שלה שקול לקצב של n^2, עד כדי כפל בקבוע. אפשר לבחון זאת על ידי חסימת f(n) מלמטה ומלמעלה על ידי הפונקציה c*n^2 כאשר c קבוע כלשהו:
קוד:
מצד אחד:
f(n) = n*(n-1)/2 = 1/2 * (n^2 - n) <= 1/2 * n^2 <= n^2
מצד שני:
f(n) = n*(n-1)/2 = 1/2 * (n^2 - n^2/n) = 1/2 * (1 - 1/n) * n^2 >=
>= 1/2 * (1-0) * n^2 = 1/2 * n^2
|
|
|
במונחים של סדר גודל, ניתן לומר ש-f(n) היא ת'תה (אות יוונית) של n^2.
יכול להיות שזה יותר מדי בשביל השלב הנוכחי שלך, אבל אני לא חושב שאפשר לתאר את זה יותר בפשטות כדי באמת להבין את המושג של סדר גודל.
כדי לך על כל מקרה לקרוא קצת על O, ת'תה ואומגה - הסימונים שמתארים סדרי גודל.
__________________
דלתות אדריכלים גגות פוליש
|
| חזרה לתחילת העמוד |
|
| |
yiag
משתמש פעיל
הצטרף / הצטרפה: 26 May 2006
מדינה: Israel
משתמש: מנותק/ת
הודעות: 103
|
| נשלח בתאריך: 06 January 2007 בשעה 21:35 | | IP רשוּם
|
|
|
|
מופ כתב:
היי שלום..
ואיך אפשר לחשב את זה .אם אפשר בכלל? כלומר אני יודע שהכי יעיל זה n log n אבל איך מחשבים את זה?
תודה
|
|
|
הכי יעיל זה log n לא n log n
|
| חזרה לתחילת העמוד |
|
| |
נושאים פעילים
רשימת משתמשים
חיפוש
עזרה
הרשמה
התחברות
UnderWarrior Forums : 
תיכנות
