האם אפשר לפתור את התרגיל הבא בסיבוכיות נמוכה יותר ממה שפתרתי

[falukky]

אני צריך לכתוב פונקציה שמקבלת מערך מלא במספרים ומחזירה true אם יש מספר מסויים שמופיע רק פעם אחת ו-false אחרת.

לא מצויין אם המערך ממוין או לא אז חשבתי:

1. למיין את המערך - logn

2. לכתוב פונקציה שעוברת פעם אחת על המערך ובודקת אם יש מופע יחיד של מספר מסויים - n

ובסה"כ Onlogn

האם יש אפשרות לפתור את זה למשל בסיבוכיות של n ?

[שניצל]

מיון של מערך זה nlogn, לא רק logn (אבל שאר החישוב שלך נכון).

אבל כן, יש דרכים יותר יעילות, השאלה היא האם למדת אותן...

[falukky]

ישנה אפשרות לפתור את זה מבלי למיין את המערך קודם (נמוך מ-n²) ?

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

אגב אם המיון זה nlogn והפונקציה שעוברת ובודקת זה n וביחד n²logn האם זה סיבוכיות נמוכה יותר מ-n² ?

[שניצל]

כמו שאמרתי, יש דרך, אבל אני לא יודע אם למדת את מבנה הנתונים שאתה צריך בשבילה.

n ועוד nlogn זה לא n²logn.

[falukky]

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

לא, לא למדתי מבנה נתונים, זה קורס מבוא למדעי המחשב ושפת ג'אווה

אני פשוט רוצה להבין אם הפיתרון שלי שיהיה n + nlogn יתקבל כי רשום בפירוש בשאלה השיטה שתכתבו צריכה להיות יעילה ככל הניתן. תשובה שאינה יעילה מספיק, כלומר שתהיה בסיבוכיות גדולה יותר מזו הנדרשת לפתרון הבעיה לא תקבל את מלוא הנקודות..

אני מתאר לעצמי שהם לא יקבלו פיתרון של n², אבל השאלה היא אם זה מספיק

[שניצל]

תחזור קצת על החומר של סיבוכיות. n+nlogn זה זהה ל-nlogn (כמו שאמרתי, התוצאה הסופית נכונה).

אין לי מושג איזו תשובה הם יקבלו.

למדת על טבלאות גיבוב (hash)?

[falukky]

לא

[שניצל]

אז הפתרון שלך הוא כנראה הכי יעיל כרגע בשבילך.

[Gil28]

אלא אם כן יש לו איזו הנחה על טווח הערכים שבמערך.

בכל מקרה כשמבקשים ממך מימוש יעיל בקורס מבוא, מתכוונים שלא תביא פתרון נאיבי (במקרה הזה n^2)

[falukky]

תודה רבה