חשבתי על שאלה לא פשוטה ב- JAVA שעלולה להופיע בבחינה...

אם אני מעוניין לכתוב שיטה שמקבלת מערך באורך שאינו ידוע אשר בודקת האם המערך הינו פולינדרום בסיסוכיות O(n)

האם זה אפשרי ע"י זה שלא ידוע אורך המערך ובכלל בסיבוכיות הנ"ל ?

אם כן אשמח להצעת אלגוריתם פשוט ויעיל תודה !

לא ברור מה הכוונה ב "מערך באורך שאינו ידוע", אם הוא לא יודע, אז מה המשמעות של O(N)?

זה אמור להיות מעניין באיזושהי צורה ? :s05:

תעשה לולאה אחת שעוברת על המערך רק בשביל לדעת מה האורך שלו (נניח אורך=N)

לולאה שניה שרצה ומשווה בין המערך במיקום I לבין מיקום N-I באם הוא שונה התוצאה היא "לא" באם הגענו לI*2 =N אזי התשובה "כן"

סה"כ רצנו פעמיים על המערך ולכן הסיבוכיות היא 2N~N

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

ניסיתי, ועדיין קשה לי לחשוב על שאלה יותר קלה מזאת...

השאלה הזאת לא ממש קשה... במיוחד אם יש לך פונקציה שמחזירה אורך מערך כמו בC#

ב JAVA אין דבר כזה מערך שלא ידוע אורכו. לכל מערך יש משתנה בשם length שנותן את המידע המבוקש

למשל

private void someMethod(byte[] b)
{
	int i = b.length ;
{

זה אמור להיות מעניין באיזושהי צורה ?

מצחיק מאוד ....

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

אני חושב שזה אחלה פתרון... למרות שלא צריך מחסנית ניתן להעביר למערך שני שאורכו כמחצית מאורך המערך הנתון...

למשל

private void someMethod(byte[] b)
{
	int i = b.length ;
{

אבל למה ככה ???

פשוט בלולאה לשים את

b.length

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

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

ניתן גם לעשות את זה ברקורסיה.

מה זה למה ככה.... לא באתי לתת פתרון מלא לבעיה. הדגמתי שכל מערך בג'אווה תמיד ידוע האורך שלו, גם אם הוא ארגומנט למתודה.

אם אתה מגדיר מחסנית או מערך נוסף, אתה מוסיף גם סיבוכיות מקום ואז זה לא בדיוק O)N(

אז כמה זה בדיוק ? O)N+1( ? אפשר להפסיק להתפלפל בשאלה הלא הגיונית הזו ?

מצחיק מאוד ....

אני חושב שזה אחלה פתרון... למרות שלא צריך מחסנית ניתן להעביר למערך שני שאורכו כמחצית מאורך המערך הנתון...

אבל למה ככה ???

פשוט בלולאה לשים את

b.length

זה לא מצחיק, זה עצוב.

גם ישבתי לענות לך גם ירדת על התשובה שלי והצעת פתרון שהוא לא יותר טוב ממה שהצעתי.

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

ואז תודה למגיבים שוב שלא רק שהם השקיעו מזמנם לנסות לעזור לך אלא שגם בזכותם למדת משו והגעת לפתרון השאלה שלך.

ולגבי המצחיק\עצוב - השאלה הזו מגיעה ממבחן ביתספר או מקורס ראשוני בתחום ? איפה אתה לומד ?

וואי וואי ווווואאייי! תרגעו כבר יאללה איתכם! מה נסגר?! לא כל אחד מתכנת שנים כמוכם.

בכל מקרה, הם צודקים. בג'אווה אין דבר כזה מערך באורך לא ידוע.

הפיתרון שלי (אגב לי נתנו את אותה שאלה רק שהמערך בעצם היה מספר והיה צריך לפרק אותו למערך לפני כן)

הוא למצוא את אורך המערך ואז לשים שני אינדקסים שהראשון (A) הוא בתחילת המערך והשני (B) בסופו ואז לעשות לולאה באורך חצי המערך.

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

את הלולאה אתה יכול לעשות ב WHILE כאשר התנאי הוא שכל עוד A<=B יש להמשיך. ככה אתה פותר את הבעייה של מערכים זוגיים\אי זוגיים.

בהצלחה.

נ.ב. שכחתי סיבוכיות - סך מספר הפעולות הוא חצי N אז הסיבוכיות היא O של N.

הפיתרון שלי (אגב לי נתנו את אותה שאלה רק שהמערך בעצם היה מספר והיה צריך לפרק אותו למערך לפני כן)

הוא למצוא את אורך המערך ואז לשים שני אינדקסים שהראשון (A) הוא בתחילת המערך והשני (B) בסופו ואז לעשות לולאה באורך חצי המערך.

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

את הלולאה אתה יכול לעשות ב WHILE כאשר התנאי הוא שכל עוד A<=B יש להמשיך. ככה אתה פותר את הבעייה של מערכים זוגיים\אי זוגיים.

בהצלחה.

נ.ב. שכחתי סיבוכיות - סך מספר הפעולות הוא חצי N אז הסיבוכיות היא O של N.

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

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

ניתן גם לעשות את זה ברקורסיה.

נראה לי הפיתרון הכי טוב.

אז כמה זה בדיוק ? O)N+1( ? אפשר להפסיק להתפלפל בשאלה הלא הגיונית הזו ?

תתפלא אבל סיבוכיות מקום תופסת חלק נכבד וכדאי להתחשב גם בה.

כן, רק שלהוסיף מחסנית ו/או מערך נוסף (או שתיהם) עדיין נחשב ל O)N( בדיוק (בתוכנית הזו).

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