שלום,

אני תקוע על תרגיל ב- C ואין לי מושג איך לגשת אליו.

מבקש את עזרתכם, תודה!!

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

בגדול, אפשר לעשות לולאת for שתרוץ עבור כל אינדקס ותבדוק אם הערך שלו כבר קיים באינדקס אחר.

אבל זה יהיה סדר גודל של n^2 אם אני לא טועה.

סבבה, זה בדיוק הפתרון.

עכשיו צריך לחשוב על יעילות. מה מזכיר לך nlogn? (זה בדרך כלל רמז די גדול)

מס' הפעולות (המשוערך) שיש לבצע כדי להגיע לפיתרון הוא ערך הקלט n כפול לוג שלו בבסיס 2.

אם n=8 אז מס' פעולות הוא 8x3 (לערך).

השאלה היא איך אני מתרגם את זה לקוד?

תחשוב - אילו פעולות על מערך עוזרות לעבוד על ערכים שלו?

אני מציע להתנתק לחלוטין מקו המחשבה המקורי של הלולאה המקוננת בn^2.

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