משימה 6 - יעילות

מנהל: The Architect

נעול
Arco
הודעות: 15
הצטרף: 00:10 19/11/2008

משימה 6 - יעילות

שליחה על ידי Arco » 22:13 07/01/2009

מה מידת החשיבות ליעילות בסעיף זה?

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

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

האם אפסיד נקודות, האם הפיתרון שלי נחשב לא קביל אולי עד כדי אפס נקודות?

yurib
הודעות: 207
הצטרף: 18:30 19/11/2008

שליחה על ידי yurib » 15:36 09/01/2009

לפי הFAQ בדיקות עבור n-ים גדולים יעשו ע"י פונקציה שלהם שיודעת להתמודד עם זה, מה שיבדק במקרים הללו זה האם בנית את ה CNF נכון. התוכנית שלך אמורה להתמודד עם n=8 לפחות בזמן של פחות מ 10 שניות.
עכשיו, אתה אומר שאתה מצליח להתמודד עם עד 20 פסוקיות בלי בעיה, זה נשמע קצת מוזר כי כבר ב n=4 מספר הפסוקיות (אם בנית את הCNF לפי השיטה שמוזכרת בתרגיל) גדול בהרבה מ 20 ובn=8 יש כבר כמה מאות.
אם זה אכן המצב אני ממליץ שתראה איך אתה משפר את זמן הריצה על מנת לעמוד ביעד המינימלי...
אם התכוונת שעד n=20 אין לך בעיה, אז אין לך בעיה :)

נעול

חזור אל “- מבוא למדעי המחשב”