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

אשכול: הוכחת חסם תחתון - עץ החלטה

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

    פרטי משתמש

    ברירת מחדל הוכחת חסם תחתון - עץ החלטה

    שלום חברים.

    יש למישהו רעיון איך להוכיח את החסם התחתון הזה לאלגורית'ם שפותר את Merge_k שמבוסס על השוואות.
    אבל בעזרת ההדרכה שהם נתנו.

    תודה רבה.
    קבצים מצורפים קבצים מצורפים
    • סוג הקובץ: png עלה.png‏ (166.6 ק"ב , 3 צפיות) Let Mergek be the following problem: Given k sorted arrays, A1, ..., Ak, each ofsize , return a single sorted array A containing all n elements from A1, ..., Ak.Consider this algorithm for Mergek:Merge_k(A1, ..., Ak):B1 = A1for i=2 to k:B;= Merge (Bi-1, A;)return BnProve: N2(nlogk) is a lower-bound for the number of queries performed bya comparison-based algorithm that solves MergekGuidance: Think about how to construct an input for Mergek that hasenough permutations, i.e. enough leaves in the algorithms decision tree,that will bound the height of the tree by N(nlogk) (Notice that each arrayAi is sorted, so a simple permutation of it is not a legal input to thealgorithm). You may also want to use the claim from question 4, that abinary tree of height h has at most 2h leaves.


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

Users Browsing this Thread

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

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

הרשאות

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

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