מציאת פולינדרום

[אוֹריארד]

יעילות לינארית?? איך?../images/Emo26.gif

הרי כל בדיקה כזו (יצירה של תור דו-כיווני) היא לינארית. אבל אתה מבצע את הפעולה לכל איבר במחרוזת! כלומר - סה"כ - סיבוכיות של O של N בריבוע! כלומר - אין עדיפות על הפתרון שהצגתי בסיבוכיות הזמן. בפתרון שאני הבאתי - סיבוכיות המקום היא לינארית. בפתרון שאתה הבאת היא O של N בריבוע. כלומר - עדיין (אם הוא נכון בכלל) - הפתרון שהבאתי יותר עדיף...

 

[אינגולמו]

סליחה, יש לי טעות

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

 

[אינגולמו]

נכון,הפתרון שהצעת הוא יותר טוב../images/Emo45.gif

סתם שאלה, אפשר איכשהו לחסום את מספר החיפושים טוב יותר, לא? לדוגמה, אם מצאתי פלינדרום באורך N/2, אז אין טעם להמשיך. השאלה היא אם זה משנה את סדר גודל זמן החיפושים.... כי ככל שיש יותר פלינדרומים, אז הגודל שלהם חסום ע"י מספר קטן יותר ויותר...

 

[אלדד28]

לא, סדר הגודל של האלגוריתם

לא מתקצר על סמך הנחה כדוגמת זו שהעלית. מעבר לזה, כמו שגם מיון של חצי מערך לוקח NlogN (כי יש לו קבוע 0.5 מקדים, שנושר ממילא) - כך גם במקרה שלפנינו סדר הגודל לא יירד מ-N^2 (לפחות לא באלגוריתמים שאתם העליתם).

 

[אינגולמו]

לא הבנתי

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

 

[אינגולמו]

ועדיין נראה לי

שהאלגוריתם שהצעתי, אחרי התיקון שציינתי יכול לבצע בפחות מ-N^2. אני לא בטוח כרגע, ואני עובד על ניתוח היעילות. בגדול, כרגע זה נראה כאילו זה הולך לכיוון של NLOGN. אני מחכה להוכחה מצידך שאי אפשר להשיג פחות מ-N^2....