partition

מנהל: TA_Isana

שלח תגובה
asho
הודעות: 27
הצטרף: 19:53 28/10/2009

partition

שליחה על ידי asho » 21: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 האו הנכון.
אשמח אם מישו יסביר לי מה אני מפספס.
.

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

Re: partition

שליחה על ידי TA_Ariel » 22:07 21/05/2010

partition לא מספיק זה רק ההתחלה, אתה יכול להשתמש בPartition בשביל למצוא את החציון, ולהמשיך משם.

hades200621
הודעות: 35
הצטרף: 01:00 24/10/2009

Re: partition

שליחה על ידי hades200621 » 02:00 22/05/2010

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

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

Re: partition

שליחה על ידי TA_Ariel » 02:23 22/05/2010

לעשות את התהליך הזה פעם אחת לוקח O(n). אם תעשה את זה k פעמים אז לא.

שלח תגובה

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