partition

מנהל: TA_Isana

partition

הודעהעל ידי asho » 20:32 21/05/2010

אשמח לחידוד הנושא.
לא הבנתי איך אפשר לקבל את האיבר ה n/k בגודלו..
כאשר אנו מבצעים פרטישן אין הבטחה שיצא לנו בסופו של דבר האיבר ה a*n/k בגודלו.
למשל.
אם ניקח את סדרת המספרים הזאת 73 14 15 8 19 2 14 8 n=8 k=2.
לאחר פרטישן המערך יישאר אותו הדבר.( כיוון שכל המספרים קטנים מהפיבוט שהוא 73).
והאיבר ה "מיוחד" הראשון יהיה ( הרביעי בגודלו) 19? כייוון שהוא במחצית? והמערך שלי כבר מחולק ל n/k קבוצות?!?!?-האיבר 15 האו הנכון.
אשמח אם מישו יסביר לי מה אני מפספס.
.
asho
 
הודעות: 27
הצטרף: 19:53 28/10/2009

Re: partition

הודעהעל ידי TA_Ariel » 21:07 21/05/2010

partition לא מספיק זה רק ההתחלה, אתה יכול להשתמש בPartition בשביל למצוא את החציון, ולהמשיך משם.
TA_Ariel
 
הודעות: 261
הצטרף: 23:53 22/04/2009

Re: partition

הודעהעל ידי hades200621 » 01:00 22/05/2010

הצלחתי למצוא את האיבר ה-k בגודלו אך איני בטוח שהתוכנית עומדת בדרישות זמני הריצה... האם קריאה לאותו חלק שמכיל את גודל ה-k כל פעם בלולאה עד אשר האינדקס שיוחזר בפעולת החציון יהיה שווה לגודל ה-k שאני מחפשים? כאשר הקריאה עם ערך הפיוט הוא רנדומלי?
hades200621
 
הודעות: 35
הצטרף: 01:00 24/10/2009

Re: partition

הודעהעל ידי TA_Ariel » 01:23 22/05/2010

לעשות את התהליך הזה פעם אחת לוקח O(n). אם תעשה את זה k פעמים אז לא.
TA_Ariel
 
הודעות: 261
הצטרף: 23:53 22/04/2009


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

מי מחובר

משתמשים הגולשים בפורום זה: אין משתמשים רשומים ו 3 אורחים

cron