עמוד 1 מתוך 1

partition

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

Re: partition

הודעהפורסם: 21:07 21/05/2010
על ידי TA_Ariel
partition לא מספיק זה רק ההתחלה, אתה יכול להשתמש בPartition בשביל למצוא את החציון, ולהמשיך משם.

Re: partition

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

Re: partition

הודעהפורסם: 01:23 22/05/2010
על ידי TA_Ariel
לעשות את התהליך הזה פעם אחת לוקח O(n). אם תעשה את זה k פעמים אז לא.