שלום לכולם

נסיתי לפתור תשאלה אך לא הצלחתי להגיע לסיבוכיות קטנה יותר מ o(n²)

האם למישהו יש רעיון לפתור בסיבוכיות יעילה יותר?

תודה.

תחשוב על זה ככה:

נניח שיש לי את הרשימה cadabadab, ואני מחפש את הרשימה ab.

השיטה הנאיבית היא לעבור אות אות ברשימה הראשונה, ולראות אם הרשימה השנייה מופיעה בה החל מהמקום הזה (אני מניח שזה מה שעשית?)

שיטה קצת יותר חכמה:

נסתכל על האיבר הראשון ברשימה הראשונה - c, ונראה אם הוא תואם לאיבר הראשון ברשימה השנייה - a. הוא לא תואם.

אז נמשיך הלאה ברשימה הראשונה. האיבר הבא הוא a, והוא תואם לאיבר הראשון ברשימה השנייה! אז נתקדם בשתי הרשימות.

נשווה אז בין האיבר הבא ברשימה הראשונה (d) והאיבר הבא ברשימה השנייה (b). הם לא תואמים - אז ברשימה השנייה נחזור להתחלה, וברשימה הראשונה נמשיך הלאה.

האיבר הבא בשתי הרשימות הוא a, והוא תואם. לכן נתקדם בשתיהן. האיבר הבא בשתי הרשימות הוא b, והגענו לסוף הרשימה השנייה, מה שאומר שמצאנו מופע של הרשימה השנייה בראשונה. שוב נחזור לתחילת הרשימה השנייה ונמשיך בתהליך.

החסרון של השיטה הזו הוא שהיא מתעלמת מחפיפות: אם רשימה א היא ababab ואני מחפש את הרשימה aba, אז תיאורטית יש שני מופעים, אבל נמצא רק אחד.

אגב, אם יצא לך ללמוד אוטומטים, זה בדיוק זה.

דווקא חשבתי בדיוק על הפתרון הזה..

הסיבוכיות שלו היא לא o(n²?

הרי אתה רץ פעם אחת על הרשימה הראשונה

ובכל פעם שתפגוש את האיבר הראשון

אתה רץ n פעמים(או יותר נכון כמה פעמים שיופיע a=במקרה הגרוע על כל הרשימה) על הרשימה השניה

ונוצרת סיבוכיות של n²

אני טועה?

בנוסף אני צריך לבדוק את ענין החפיפה שכתבת

פשוט לא העלתי את זה, חשבתי שזה לא כזה רלוונטי(טעות שלי)

לדוגמא רשימה א: bbbb ואני צריך למצוא bb , היא אמורה להחזיר 3

כמו הדוגמא שלך עם הaba

הפתרון הראשון הוא n^2. הפתרון השני הוא n, אבל יש לו את החסרון שציינתי.

תכל'ס ההבדל בין שני הפתרונות הוא כזה:

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

בשיטה הראשונה, אתה חוזר אחורה ברשימה הראשונה וממשיך משם. בשיטה השנייה אתה לא. זה מה שגם גורם להבדל בסיבוכיות.

אתה בטוח שהפתרון השני הוא n???

כי למרות שאתה עובר רק פעם אחת על הרשימה הראשונה

על הרשימה השניה אתה עובר כמה וכמה פעמים?(כל פעם שאתה מוצא a ברשימה הראשונה)

תקן אותי אם אני טועה

אני משתגע

אתה בטוח שהפתרון השני הוא n???

כי למרות שאתה עובר רק פעם אחת על הרשימה הראשונה

על הרשימה השניה אתה עובר כמה וכמה פעמים?(כל פעם שאתה מוצא a ברשימה הראשונה)

תקן אותי אם אני טועה

אני משתגע

כן הפתרון השני הוא n.

תסתכל על זה ככה, אתה עובר על הרשימה הראשונה באורך n ולכל איבר ברשימה אתה עובר גם על איבר אחד מהרשימה השניה, תכל'ס זה 2n אבל לא מתייחסים למקדמים קבועים.

בדיוק. עוברים על שתי הרשימות במקביל.

תודה רבה לשניכם

אני חושב שהבנתי..

מצטער שבלבלתי את המוח יש לי ממש בעיה עם הסיבוכיות, אני מתבלבל וקשה לפעמים להבין.