שלום לכולם.
אני צריכה לכתוב תוכנית העומדת בסיבוכיות מסויימת וקצת נתקעתי ואני זקוקה לעזרתכם...
התוכנית היא משחק אבן-נייר-מספריים בין מספר שחקנים. פונקציה אחת היא לקלוט שחקנים לתוכנית בסיבוכיות (o(logn, עשיתי קליטה לעץ AVL כשבכל node קלטתי מספר שחקן, מספר משחקים ששיחק ומספר נקודות שצבר וכמובן שהקליטה היא לא לפי סדר, ועמדתי בסיבוכיות. פונקציה אחרת היא להציג את פרטי השחקן שמספר הזיהוי שלו X בסיבוכיות (o(log n, הוצאתי איבר X מהעץ AVL שכלל את כל הפרטים שהכנסתי ועמדתי בסיבוכיות. פונקציה אחרת היא להזין את פרטי המשחק, הכוונה לשני המשתתפים, למה שבחרו ועדכון מספר המשחקים ששיחקו ומספר הנקודות שצברו בסיבוכיות (o(n, וגם בזה עמדתי.
נשארו לי עוד 2 פונקציות, האחת לחשב את דירוג שחקן X בליגה בסיבוכיות (o(d כאשר d הוא הדירוג והשניה היא הצגת y מקומות ראשונים בליגה בסיבוכיות (o(y. את 2 הפונקציות האלה אין לי מושג איך לעשות ולעמוד בסיבוכיות... יש לי את הסיבוכיות (o(n שלא ניצלתי עד הסוף בפונקציית הזנת פרטי המשחק. חשבתי על מערך בעל n איברים כאשר n[0]=1, n[1]=2 וכו', שזה אומר המקומות ומכל תא יוצא פויינטר ל-node המתאים לפי מיקום השחקן אבל זה לא עומד בסיבוכיות. אפשרות נוספת היא בניית מערך שייקבל בכל תא ערך של מספר נקודות ופויינטר ל-node המתאים וימויין לפי מספר נקודות אבל גם זה לא עומד בסיבוכיות.
יש למישהו רעיון שיכול לעזור לי, בבקשה? זו עבודת חובה שאני חייבת להגיש...
מה אני יכולה לעשות ואם הפיתרון זה מערך, איפה אני צריכה לבנות אותו ועדיין לעמוד בסיבוכיות?
מצטערת על אורך השאלה ותודה מראש לכל העונים. :-)

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

אולי אם תשתמשי בעוד עץ AVL אבל שהפעם יהיה ממוין לפי הדירוג ובנוסף תחברי את העלים ברשימה דו כיוונית עם מצביע לעלה הגדול ביותר.
הכנסה לשני העצים ביחד עדיין תישאר log(n) וכעת תוכלי לחשב את הדירוג של שחקן X ע"י מציאתו ברשימה של העץ (מתחילים בדירוג הגבוה ביותר ויורדים עד שמוצאים אותו) וגם להדפיס את Y הדירוגים הגבוהים בסיבוכיות של Y (פשוט לעבור על הרשימה).

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

בהצלחה