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

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

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

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

ובסה"כ Onlogn

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

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

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

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

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

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

נערך 2014 בינואר 1111 שנים על-ידי falukky

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

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

נערך 2014 בינואר 1111 שנים על-ידי שניצל

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

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

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

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

נערך 2014 בינואר 1111 שנים על-ידי falukky

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

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

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

לא

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

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

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

תודה רבה