עבודה 6 שאלה 1ב

מנהל: TA_Isana

שלח תגובה
wizard
הודעות: 18
הצטרף: 17:35 10/01/2009

עבודה 6 שאלה 1ב

שליחה על ידי wizard » 21:31 14/07/2009

אני אפילו לא מבין אם יש טעות בשאלה או שיש פשוט משהו שאני מפספס.
בשאלה אנחנו מתבקשים לשפר את האלגוריתם באמצעות שימוש בפונקציה המחזירה לנו את החציון של המערך A בזמן O(n) o. (נא לא להתייחס ל o זה רק ע"מ ליישר את האנגלית).
במידה ונשתמש בפונקציה זו בכל מקום שבו לא נחזיר את ערכה לx, ז"א נשתמש בה בתוך הלולאה, בהכרח לא נשפר את זמן הריצה, אזי הזמן יהיה O(n^2) o.
מעבר לזה, אם מניחים שאופן הקריאה ל partition ב Quicksort הוא עם המשתנים p,r אז איך מציאת אותו חציון כל פעם מחדש עוזרת לנו??? הרי אנחנו לא מקטינים את A וקוראים לפונקציית מציאת החציון עם אותו מערך בקריאה הרקורסיבית בQuicksort עצמו...
חוץ מזה, לא נותר מקום בהחזרת j להביא את x למקומו ולכן איך שאני לא חושב על זה אני לא מבין איך בהתחשב בעובדה שx הוא מיקומו של החציון j אי פעם יהיה שונה מהערך התחתון של n/2 ואיך אני מביא את החציון למקומו...

אם מישהו יכול להסביר לי למה אני בכלל לא בכיוון או לתת איזשהו רמז, אודה לכם...

למתרגלים - אני חושב שעכשיו שאנחנו קרובים כל כך למבחן ולמבחנים אחרים, ניתן לעזור לנו קצת יותר כאן בפורום ולייעל את הזמן שלכם בשעות הקבלה. רוב התשובות שניתנות כאן בפורום הן רמזים עלומים שלרוב לא מכווינים לפתרון ולא תורמים להבנתו. בסופו של דבר אנו מוצאים את עצמנו מגיעים לשעות קבלה ו"מבזבזים" כשעה וחצי על המתנה לתורנו לשאול ואכן מקבלים את התשובה... אז אפשר לחסוך זאת באמצעות הפורום שנקרא גם - help forum ונראה לי שהכוונה היא שנקבל פה עזרה...

שלח תגובה

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