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

אשכול: טעויות נפוצות בהוכחת סיבוכיות באינדוקציה

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

    פרטי משתמש

    ברירת מחדל טעויות נפוצות בהוכחת סיבוכיות באינדוקציה

    שלום חברים.

    המסגרת התחתונה אומרת מה הבעיה במסגרת העליונה.
    אבל במסגרת העליונה כן התייחסו לאותו c, עשו קטן-שווה 2c*n/2 + n
    כלומר, כן יש התייחסות לקבוע c.
    אז איפה הבעיה באינדוקציה?










    תודה רבה.
    קבצים מצורפים קבצים מצורפים
    • סוג הקובץ: png עלה.png‏ (125.7 ק"ב , 11 צפיות) נתבונן בנוסחת הנסיגה הבאה:T(n)=2T (g)+n. ננחש כי ( T=O (n , נבחר קבוע c כלשהו (המקיים את הבסיס), עתה באינדוקציה שלמה נקבל (T(n)=2T (g)+n <2c4+n=O (n. איפה טעינו? הרי ממקרה 2 של משפט האב אנחנו יודעים ש- (T(n)=6 (nlog.n. הטעות היא שכאשר אנחנו קובעים c, עלינו לדבוק בו לאורך כל האינדוקציה. במקרה זה עברנו באמצע לנוטציית-0] ולמעשה לא הוכחנו את צעד האינדוקציה כהלכה._


  2. #2
    משתמש רשום משתמש מתחיל

    פרטי משתמש

    ברירת מחדל

    בסוף יוצא לך $n\cdot (c+1)$ וזה לא אותו $c+1$ שונה מ-$c$ שעליו התחייבת בהנחת האינדוקציה.
    אהבתי Helpme אהב \ אהבו את התגובה
     

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

    פרטי משתמש

    ברירת מחדל

    ציטוט פורסם במקור על ידי ThePrince צפה בהודעה
    בסוף יוצא לך $n\cdot (c+1)$ וזה לא אותו $c+1$ שונה מ-$c$ שעליו התחייבת בהנחת האינדוקציה.
    אה.
    כי הנחנו נכונות עבור כל מי שקטן מ-n בעזרת c חיובי מסוים, אז צריך להראות שאותו c בדיוק הוא גם זה שמקיים בדיוק את הצעד (n)?
    תודה רבה.


  4. #4
    משתמש רשום משתמש מתחיל

    פרטי משתמש

    ברירת מחדל

    כן
    אהבתי Helpme אהב \ אהבו את התגובה
     

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

Users Browsing this Thread

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

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

הרשאות

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

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