שאלה על זמנים ממוצעים

מנהל: TA_Isana

michal cohen
הודעות: 87
הצטרף: 19:04 11/11/2009

שאלה על זמנים ממוצעים

שליחה על ידי michal cohen » 13:35 18/05/2010

אם אני משתמשת בpartition כ-k פעמים, ככה שזה מחלק לי את המערך ל-k קבוצות כל אחת בגודל n/k... אז זה בעצם חלוקה ממוצעת.
כלומר יש לי בממוצע n/k איברים בקבוצה עם חריגות קטנות לכאן או לכאן. נכון?
ואם כן, אז נניח אני רוצה לעשות העברות מקבוצה לקבוצה ככה שיהיו בדיוק n/k איברים בקבוצה.
אז לכל היותר יש לי חריגה של n/k איברים ולכן יש לי בעצם קבוצה של n/k ואחריה קבוצה של 0 איברים, קבוצה של n/k ואחריה קבוצה של 0 איברים וכן הלאה.
ואז יש לי להעביר לכל היותר k/2 * n/k איברים שזה יוצא ב-O(n נכון?
אני צודקת? כי בתכלס אם זה זמנים ממוצעים אז בממוצע אני לא אחרוג מהם כי יש לי בממוצע n/k איברים בקבוצה...
מקווה שהבהרתי את מה שניסיתי לשאול....

TA_Ariel
הודעות: 261
הצטרף: 00:53 23/04/2009

Re: שאלה על זמנים ממוצעים

שליחה על ידי TA_Ariel » 14:52 18/05/2010

partition מחלק את המערך ל2 חלקים 1/4 ו4\3 בממוצע.
k פעמים partition לא יתן לך בממוצע קבוצות בגודל n/k.
מצד שני אפשר להשתמש בpartition בשביל למצוא את האיבר n/k בגודלו בזמן o(n).

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

michal cohen
הודעות: 87
הצטרף: 19:04 11/11/2009

Re: שאלה על זמנים ממוצעים

שליחה על ידי michal cohen » 15:38 18/05/2010

שתי שאלות:
1. התכוונתי לבצע פרטישן logk פעמים וזה ייתן לי קבוצות בגודל n/k בממוצע. (כמו מתי n/2^i=n/k כאשר i=logk)
2. לא ברור לי איך נשתמש במציאת האיבר ה-n/k כי זה לוקח O(n) וצריך לעשות את זה k פעמים סה"כ O(k*n).
למה הדרך שלי לא נכונה?

TA_Ariel
הודעות: 261
הצטרף: 00:53 23/04/2009

Re: שאלה על זמנים ממוצעים

שליחה על ידי TA_Ariel » 16:06 18/05/2010

partition ראשון מחלק את המערך לרבע ושלושה רבעים,
מה את עושה אחרכך? על מה מתבצע הpartition השני? על השני המערכים שקיבלת באיטרציה הקודמת?



לגבי 2 זה נכון. זה רק בסיס לרעיון.

michal cohen
הודעות: 87
הצטרף: 19:04 11/11/2009

Re: שאלה על זמנים ממוצעים

שליחה על ידי michal cohen » 16:45 18/05/2010

יכול להיות שב-2 חישבתי את הזמני ריצה לא נכון?
כי תכלס הנוסחאת נסיגה למציאת האיבר ה-i בגודלו היא:
T(n)=2T(n/2) + O(n) x
ואז אני אעשה i איטרציות ואגלה ש-i שווה ל-logk (כי אני רוצה לעצור כשהמערך בגודל n/k) ואז זה דווקא מסתדר יפה לא? זה יוצא בדיוק זמן ריצה של nlogk....
הבנתי נכון? כאילו מצאתי את כל האיברים ה-a*n/k לא?

TA_Ariel
הודעות: 261
הצטרף: 00:53 23/04/2009

Re: שאלה על זמנים ממוצעים

שליחה על ידי TA_Ariel » 17:10 18/05/2010

חישבת נכון בפעם הראשונה. המערך לא קטן פי שניים כל פעם, הוא קטן בn/k.
נניח k=n/2 זה אומר שזמן הריצה הוא O(n*n).

עכשיו תחשבי שk הוא חזקה של שניים כלומר k=2^i.
מציאת חציון לוקחת o(n). את מחלקת את המערך לשניים(קטנים וגדולים מהחציון) גודל המערכים שווה(עד כדי 1).
עכשיו חוזרים על אותה פעולה במערכים הקטנים שוב בזבזנו O(n). ככה מצאת את איברים במקומות n/2 3*n/4 n/4.

כמה איטרציות את צריכה עד שתמצאי את כל האיברים?

michal cohen
הודעות: 87
הצטרף: 19:04 11/11/2009

Re: שאלה על זמנים ממוצעים

שליחה על ידי michal cohen » 17:49 18/05/2010

כנראה לא הסברתי את עצמי טוב....
אני כל פעם רוצה למצוא את האיבר ה-a*n/k בגודלו.
אם אני קוראת לפונקציית מציאת האיבר ה-i עם מערך בגודל n אז אני אחפש את האיבר ה-(k/2) * (n/k) בגודלו...
ואז יש לי n/2 איברים שקטנים ממנו ו-n/2 איברים שגדולים ממנו....
וכך חוזר חלילה.
ז"א אני לא מחפשת פה חציונים... אני מחפשת בדיוק את האיברים המיוחדים רק שכל פעם אני מחשבת איזה איבר מתאים לי לפי גודל המערך...
אח"כ למשל ... אם אני קוראת לפונקציית מציאת האיבר ה-i בגודלו עם החצי השמאלי של המערך (האיברים הקטנים...) אז אני אחפש את האיבר ה-(k/2)*(k/2) * (n/k) בגודלו....
זה נכון?

TA_Ariel
הודעות: 261
הצטרף: 00:53 23/04/2009

Re: שאלה על זמנים ממוצעים

שליחה על ידי TA_Ariel » 18:09 18/05/2010

לפי מה שכתבת האיבר הראשון שאת מוצאת הוא בדיוק החציון.
אחר כך את מחפשת את האיבר ה-(k/2)*(k/2) * (n/k? זה עלול להיות גדול מ-n.

אם הרעיון שלך לחפש בשלב בשני את האיברים בקמות 1\4 ו 3\4 זה לא מה שכתבת (כלומר החציונים של המערכים הקטנים),
אבל את בכיוון. את רק צריכה לחשב יותר טוב איזה איברים את מחפשת.

michal cohen
הודעות: 87
הצטרף: 19:04 11/11/2009

Re: שאלה על זמנים ממוצעים

שליחה על ידי michal cohen » 13:20 19/05/2010

התכוונתי שאחרי שמצאתי את האיבר ה-(k/2)*(n/k)אני אחפש בתת המערך השמאלי (של כל המספרים שקטנים ממנו) את האיבר ה-(k/4)*(n/k)...(וככה גם בתת המערך הימני).
ככה אני אמשיך עד שאני אגיע למערכים בגודל n/k... שזה יקרה באיטרציה ה-i כאשר k/2^i=1 כלומר 2^i=k כלומר i=logk.
עכשיו נראה לי כתבתי את זה נכון.... :)

TA_Ariel
הודעות: 261
הצטרף: 00:53 23/04/2009

Re: שאלה על זמנים ממוצעים

שליחה על ידי TA_Ariel » 13:55 19/05/2010

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

shaysw
הודעות: 78
הצטרף: 16:23 08/11/2008

Re: שאלה על זמנים ממוצעים

שליחה על ידי shaysw » 19:02 20/05/2010

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

TA_Ariel
הודעות: 261
הצטרף: 00:53 23/04/2009

Re: שאלה על זמנים ממוצעים

שליחה על ידי TA_Ariel » 20:32 20/05/2010

לגבי חזקות של 2. ונניח גם שn הוא חזקה של 2.
החציון בכל חלוקה מצטרף למערך של הקטנים. אתה בונה גם רשימה של האיברים במקומות המיוחדים,
החציון נכנס בתחלה בדיוק באמצע הרשימה הזו, לאחר מכן החציונים של המערכים הקטנים נכנסים למקומות שלהם ברשימה, בדיוק אמצע הדרך מהתחלה \ סוף הרשימה למקום של החציון.

לאחר logk סיבובים המערכים בגודל n/k ויש לך את כל האיברים במקומות המיוחדים. אם n לא חזקה של 2 נדרשות מעט התאמות, אבל אתה יכול להניח שזה לא המצב.

shaysw
הודעות: 78
הצטרף: 16:23 08/11/2008

Re: שאלה על זמנים ממוצעים

שליחה על ידי shaysw » 20:46 20/05/2010

תודה על התגובה המהירה, אבל עדיין לא הבנתי- נתון ש-n חזקה של 2? ומה לגבי K? הוא בטח לא חזקה של 2 ולכן לא הבנתי את כל הדיון שלכם

TA_Ariel
הודעות: 261
הצטרף: 00:53 23/04/2009

Re: שאלה על זמנים ממוצעים

שליחה על ידי TA_Ariel » 21:36 20/05/2010

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

motyr
הודעות: 36
הצטרף: 16:53 19/10/2009

Re: שאלה על זמנים ממוצעים

שליחה על ידי motyr » 13:01 22/05/2010

אני מתנצל על הבורות אבל האמת שחיפשתי במחברת ועדיין לא מצאתי תשובה לשאלה - מה זה Partition?

שלח תגובה

חזור אל “- מבני נתונים 2010”