שאלה בנושא לולאות וסיבוכיות

[shayke 0 0 7]

שאלה בנושא לולאות וסיבוכיות

חברים, אני יודע שזו שאלה של פעור.. אבל אפשר כמה דוגמאות בJAVA או בC++ לגבי מימוש אלגוריתמים שהסיבוכיות שלהם היא מעריכית? ב..הרבה הרבה הרבה תודות מראש..

 

[vinney]

לפעמים כדאי להכיר את

הקלאסיקות

 

[shayke 0 0 7]

תודה, את ההנואי יצא לי ללמוד ביחידה 15 במבוא,

אבל בהנואי מדובר בסיבוכיות ריבועית, לא?

 

[vinney]

כנראה שלא למדת טוב

הבעיה הקלאסית היא בסיבוכיות 2 בחזרת N, כשN זה מספר הטבעות.

 

[vinney]

*בחזקת, כמובן../images/Emo13.gif

 

[shayke 0 0 7]

תודה.עברתי על האלגוריתם של האנוי בשפת C

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

עכשיו רק נשארה עבודה שחורה של תיעוד-API(תיעוד בין שורות אני רושם תוך-כדי..) וזהו(סוף סוף הלילה הלבן).. מקווה שייסלחו לי על הגשה באיחור..

 

[1ca1]

דוגמאות לא חסר

לממש בחירת כל תתי הקבוצות האפשריות מתוך קבוצה נתונה (שכמובן אתה חייב לפחות לעבור על כולן, שזה 2 בחזקת גודל הקבוצה), זה בד"כ נעשה בעזרת רקורסיה (אבל יש כמה שיטות). בכל מקרה, בעיות צביעה בד"כ מחייבות מעבר על כל האפשרויות (מתקשר לNP, בכלל לכל בעיית NP יש מוודא (verifier) פולינומיאלי, אז אחת השיטות היא לבחור setting כלשהו באופן לא דטרמיניסטי (=שקול למעבר על כל האפשרויות) ולהריץ עליו את המוודא הפולינומיאלי), אז באופן כללי כל בעיית NP ניתנת לפתירה בפתרון מעריכי (יש בעיות שהן EXPTIME, זה כבר עניין אחר).

 

[shayke 0 0 7]

תודה רבה, פתרתי את התרגיל

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

 

[1ca1]

נכון

הבעיה שאתה מתאר שמה הוא subset sum שהיא NP-Complete ולכן מאוד מאוד מאוד מאוד לא סביר (לדעת מרבית העולם כיום) שקיים לה אלגוריתם הכרעה פולינומיאלי. מצד שני, ידוע אלגוריתם שהוא FTAPS (Fully Time APproximation Scheme) לבעיה, זה אומר שזמן הריצה שלו פולינומיאלי ב אחד חלקי אפסילון ובאורך הקלט (ביותר כלליות, O(n^2/epsilon))