פורסם 2009 ביולי 816 שנים שלום לכולם נסיתי לפתור תשאלה אך לא הצלחתי להגיע לסיבוכיות קטנה יותר מ o(n²) האם למישהו יש רעיון לפתור בסיבוכיות יעילה יותר? תודה.
פורסם 2009 ביולי 816 שנים תחשוב על זה ככה:נניח שיש לי את הרשימה cadabadab, ואני מחפש את הרשימה ab.השיטה הנאיבית היא לעבור אות אות ברשימה הראשונה, ולראות אם הרשימה השנייה מופיעה בה החל מהמקום הזה (אני מניח שזה מה שעשית?)שיטה קצת יותר חכמה:נסתכל על האיבר הראשון ברשימה הראשונה - c, ונראה אם הוא תואם לאיבר הראשון ברשימה השנייה - a. הוא לא תואם.אז נמשיך הלאה ברשימה הראשונה. האיבר הבא הוא a, והוא תואם לאיבר הראשון ברשימה השנייה! אז נתקדם בשתי הרשימות.נשווה אז בין האיבר הבא ברשימה הראשונה (d) והאיבר הבא ברשימה השנייה (b). הם לא תואמים - אז ברשימה השנייה נחזור להתחלה, וברשימה הראשונה נמשיך הלאה.האיבר הבא בשתי הרשימות הוא a, והוא תואם. לכן נתקדם בשתיהן. האיבר הבא בשתי הרשימות הוא b, והגענו לסוף הרשימה השנייה, מה שאומר שמצאנו מופע של הרשימה השנייה בראשונה. שוב נחזור לתחילת הרשימה השנייה ונמשיך בתהליך.החסרון של השיטה הזו הוא שהיא מתעלמת מחפיפות: אם רשימה א היא ababab ואני מחפש את הרשימה aba, אז תיאורטית יש שני מופעים, אבל נמצא רק אחד.אגב, אם יצא לך ללמוד אוטומטים, זה בדיוק זה.
פורסם 2009 ביולי 816 שנים מחבר דווקא חשבתי בדיוק על הפתרון הזה..הסיבוכיות שלו היא לא o(n²?הרי אתה רץ פעם אחת על הרשימה הראשונהובכל פעם שתפגוש את האיבר הראשוןאתה רץ n פעמים(או יותר נכון כמה פעמים שיופיע a=במקרה הגרוע על כל הרשימה) על הרשימה השניהונוצרת סיבוכיות של n²אני טועה?בנוסף אני צריך לבדוק את ענין החפיפה שכתבתפשוט לא העלתי את זה, חשבתי שזה לא כזה רלוונטי(טעות שלי)לדוגמא רשימה א: bbbb ואני צריך למצוא bb , היא אמורה להחזיר 3כמו הדוגמא שלך עם הaba
פורסם 2009 ביולי 816 שנים הפתרון הראשון הוא n^2. הפתרון השני הוא n, אבל יש לו את החסרון שציינתי.תכל'ס ההבדל בין שני הפתרונות הוא כזה:בשני הפתרונות, אתה מתקדם על שתי הרשימות (כאשר בראשונה אתה כל פעם מתחיל באיבר הבא, ובשנייה אתה תמיד מתחיל מההתחלה), ומשווה ביניהם. ההבדל הוא מה שאתה עושה כשאתה מגיע לאיבר שבו הן לא שוות, או שנגמרת לך הרשימה השנייה.בשיטה הראשונה, אתה חוזר אחורה ברשימה הראשונה וממשיך משם. בשיטה השנייה אתה לא. זה מה שגם גורם להבדל בסיבוכיות.
פורסם 2009 ביולי 816 שנים מחבר אתה בטוח שהפתרון השני הוא n???כי למרות שאתה עובר רק פעם אחת על הרשימה הראשונהעל הרשימה השניה אתה עובר כמה וכמה פעמים?(כל פעם שאתה מוצא a ברשימה הראשונה)תקן אותי אם אני טועה אני משתגע
פורסם 2009 ביולי 816 שנים אתה בטוח שהפתרון השני הוא n???כי למרות שאתה עובר רק פעם אחת על הרשימה הראשונהעל הרשימה השניה אתה עובר כמה וכמה פעמים?(כל פעם שאתה מוצא a ברשימה הראשונה)תקן אותי אם אני טועה אני משתגע כן הפתרון השני הוא n.תסתכל על זה ככה, אתה עובר על הרשימה הראשונה באורך n ולכל איבר ברשימה אתה עובר גם על איבר אחד מהרשימה השניה, תכל'ס זה 2n אבל לא מתייחסים למקדמים קבועים.
פורסם 2009 ביולי 816 שנים מחבר תודה רבה לשניכם אני חושב שהבנתי.. מצטער שבלבלתי את המוח יש לי ממש בעיה עם הסיבוכיות, אני מתבלבל וקשה לפעמים להבין.
ארכיון
דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.