פורסם 2008 בנובמבר 2216 שנים למיטב הבנתי בהוכחת נכונות לאלגוריתמים צריך גם להוכיח שזה האלגוריתם הכי יעיל שישלהוכיח שהאלגוריתם עובד זה לא קשה, אבל איך לעזאזל אני מוכיח שהוא הכי טוב שיש? כל מה שאני יודע זה שהחסם התחתון על מיון הוא O(n*log n) במקרה הכללי, וזה לא עוזר לי כי אין לי אף אלגוריתם שדורש מיוןעזרה? :-[
פורסם 2008 בנובמבר 2216 שנים 1מי אמר לך את זה? (שצריך להוכיח שהאלגוריתם שמצאת הוא הכי יעיל) זה לא נשמע הגיוני בכלל, אי אפשר לעשות כזה דבר ** למעט מקרים שבהם אתה מוכיח שלבעיה יש חסם תחתון, ואם האלגוריתם שלך עובד בסיבוכיות ששווה לזו של החסם התחתון אזי הוא הכי יעיל שאפשר. (אפשר לצמצם רק גורמי סיבוכיות קבועים)
פורסם 2008 בנובמבר 2216 שנים מחבר למיטב זכרוני, המרצה תמיד מוכיח שהאלגוריתם שהוא חירבש לנו הוא הכי טוב שניתן למצוא כחלק מהוכחת הנכונות, אני מאוד מקווה שזה לא חובה ><"
פורסם 2008 בנובמבר 2216 שנים ודאי שזה לא חובה.מצד שני, האלגוריתם צריך להיות פיזבילי.(לדוגמה, אלגוריתם מיון שרץ בסיבוכיות לא פולינומיאלית זה לא פיזבילי)
פורסם 2008 בנובמבר 2216 שנים מחבר בחיים שלי לא שמעתי את המילה הזו ם-Oבכל מקרה, גם אחד החברים שלומד איתי אומר שהוא לא מוכיח נכונות על הסיבוכיות, אז נראה שאתם צודקים, תודה
פורסם 2008 בנובמבר 2216 שנים מחבר אה, אוקי... תודה לאשכול על התוספים לפיירפוקס ולQTL שתרגם לי את המילה מאנגלית לעברית^^מבחינתי אפשר לנעול, טעות שלי, תודה על העזרה
ארכיון
דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.