מציג תוצאות 1 עד 7 מתוך 7

אשכול: מבני נתונים - Quick Select

  1. #1
    משתמש רשום חבר Emath מתקדם

    פרטי משתמש

    ברירת מחדל מבני נתונים - Quick Select

    שלום חברים.

    קיבלנו כמה שאלות לגבי האלגורית'ם של Quick Select שצירפתי בזאת.

    אם מישהו יכול יכול להסביר את 4, לתת אינטואיציה, יכול מאוד לעזור.
    זה כנראה קשור למושגים שהציגו לנו בהסתברות כמו תוחלת וכו', שאני הלכתי בזה לאיבוד, אולי אפשר לקשר את זה לכאן או משהו...

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

    תודה רבה.
    קבצים מצורפים קבצים מצורפים
    • סוג הקובץ: jpg עלה.jpg‏ (95.3 ק"ב , 18 צפיות) Quick_select(arr, left, right, k):4. Is its worst case running time equal to its average running time? (don'tif left = rightneed to write an answer just think of it)return arr[left]Assume PARTITION always returns an index ge Q2UQ3in the middleq = Partition (arr, left, right)2 quarters of the relevant sub-array, as in the following figureif k == q:return arr[k]elif k < q:return Quick_select(arr, left, q-1, k)Q1 Q2 Q3 Q4Figure 1:else:return Quick_select(arr, q+1, right, k)where the depicted array is the sub-array for which PARTITION wasPartition(arr, left, right):called (i.e. this is arrſleft..., right|).Construct the appropriate recursion formula given this assumption andx = arr[right]solve it (i.e. find the running-time's asymptotic behaviour).i = left-1for j = left to right-1if arr[j] = xi++swap(arr[j], arr[i])swap(arr[i+1], arr[right])return i+1


  2. #2
    הסמל האישי שלYes מדריך ויועץ חבר Emath מתקדם

    פרטי משתמש

    ברירת מחדל

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

    לגבי בניית נוסחת הנסיגה - פעולת החלוקה היא $O(n)$, אז אתה יכול להכניס אותה בנוסחה כ-$cn$. אם מסמנים את הנוסחה ב-$T(n)$, אז במקרה שמתמזל מזלנו וכל פעם נבחר איבר ציר טוב מקבלים משהו בסגנון של $T(n)=T(n/2)+cn,~ T(1)=1$.
    אהבתי Helpme אהב \ אהבו את התגובה
     

  3. #3
    משתמש רשום חבר Emath מתקדם

    פרטי משתמש

    ברירת מחדל

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

    לגבי בניית נוסחת הנסיגה - פעולת החלוקה היא $O(n)$, אז אתה יכול להכניס אותה בנוסחה כ-$cn$. אם מסמנים את הנוסחה ב-$T(n)$, אז במקרה שמתמזל מזלנו וכל פעם נבחר איבר ציר טוב מקבלים משהו בסגנון של $T(n)=T(n/2)+cn,~ T(1)=1$.
    אני רוצה להתעכב על כמה אמירות חשובות שלך:
    "
    במקרה הממוצע, כל פעם איבר הציר מחלק את המערך בערך לחצי" -
    איך אתה מסיק את זה? על פי מה קבעת את זה? מה האינטואיציה?
    "במקרה הגרוע, כלומר איבר הציר גרוע, אז המערך שאתה רוצה להחזיר כל פעם גדל באחד" - איך המערך יגדל באחד? כל האלגורית'ם של החלוקה, רק מקטין את המערך, לפחות ב-1. מה אני מפספס?
    "
    תחשוב למשל שכל פעם נבחר איבר הציר שהוא האיבר הקטן ביותר עד אותו שלב" - לא הבנתי מה זה אומר, שהוא הקטן ביותר עד אותו שלב.

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

    תודה רבה!


  4. #4
    הסמל האישי שלYes מדריך ויועץ חבר Emath מתקדם

    פרטי משתמש

    ברירת מחדל

    אני אענה על השאלות לפי הסדר שכתבת אותן.

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

    כמובן שהתבלבלתי, התכוונתי כל פעם קטן ב-1 (ולא יותר).

    אם לא התמזל מזלנו, אז זה לא המצב שאנחנו מדברים עליו. במקרה שזה כן, אז זה זמן הריצה:
    $$\frac{n}{1}+\frac{n}{2}+\frac{n}{4}+...+1 \leq 2n$$
    כי בכל שלב מספר האיברים לבצע עליהם חלוקה קטן פי 2.

    מקווה שזה יותר ברור...
    אהבתי Helpme אהב \ אהבו את התגובה
     

  5. #5
    משתמש רשום חבר Emath מתקדם

    פרטי משתמש

    ברירת מחדל

    ציטוט פורסם במקור על ידי Yes צפה בהודעה
    אני אענה על השאלות לפי הסדר שכתבת אותן.

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

    כמובן שהתבלבלתי, התכוונתי כל פעם קטן ב-1 (ולא יותר).

    אם לא התמזל מזלנו, אז זה לא המצב שאנחנו מדברים עליו. במקרה שזה כן, אז זה זמן הריצה:
    $$\frac{n}{1}+\frac{n}{2}+\frac{n}{4}+...+1 \leq 2n$$
    כי בכל שלב מספר האיברים לבצע עליהם חלוקה קטן פי 2.

    מקווה שזה יותר ברור...
    בעיקרון, כן הציגו לנו את האלגורית'ם של QuickSort בהרצאה, וכן הדגימו בצורה מזוויעה ביותר יש לציין את התוחלת של זמן הריצה שלמעשה יוצא nlogn - האם הבנתי משהו לגבי התוחלת של זה, איך זה נעשה, מה קורה שם? לא.

    מה שאמרת, זה באמת אינטואיציה טובה - מבחינה יותר ריגורוזית, ומבחינת הסתכלות יבשה על ההגדרה של תוחלות - אני לגמרי לא בעניינים. וזה בעיה.

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

    תודה רבה.


  6. #6
    הסמל האישי שלYes מדריך ויועץ חבר Emath מתקדם

    פרטי משתמש

    ברירת מחדל

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

  7. #7
    משתמש רשום חבר Emath מתקדם

    פרטי משתמש

    ברירת מחדל

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


מידע אודות האשכול הנוכחי

Users Browsing this Thread

כרגע 1 משתמשים צופים באשכול זה. (0 חברים ו 1 אורחים )

ביקרו באשכול זה : 6

הרשאות

  • אתה לא יכול לפרסם אשכולות חדשים
  • אתה לא יכול לפרסם תגובות
  • אתה לא יכול לצרף קבצים להודעותיך
  • אתה לא יכול לערוך את הודעותיך
  •  
אודות Emath
האתר Emath הינו יוזמה פרטית והוקם בתחילת שנת 2008 .
מטרתנו הינה למנף את הישגי התלמידים למתמטיקה ופיסיקה בארץ בכלל ובפרט בקרב תלמידי התיכון .
אנו מספקים מספר שירותים לתלמיד, ביניהם גישה למאות אלפי פתרונות איכותיים לתרגילים, פורום עזרה במתמטיקה ופיסיקה הגדול מסוגו בארץ, מאגר סיכומים, מרתונים בוידאו, פתרונות לבגרויות ועוד.
כלים אלו, מאפשרים לכל אחד, ללא תלות במיקומו, ללמוד, לתרגל ולהתמקצע על-מנת להתכונן בצורה מיטבית לבגרות במתמטיקה או פיסיקה .

לכל שאלה ניתן ליצור איתנו קשר
הצטרפו אלינו