עבור לתוכן
View in the app

A better way to browse. Learn more.
HWzone

A full-screen app on your home screen with push notifications, badges and more.

To install this app on iOS and iPadOS
  1. Tap the Share icon in Safari
  2. Scroll the menu and tap Add to Home Screen.
  3. Tap Add in the top-right corner.
To install this app on Android
  1. Tap the 3-dot menu (⋮) in the top-right corner of the browser.
  2. Tap Add to Home screen or Install app.
  3. Confirm by tapping Install.

נוסחאות נסיגה וחסם הדוק.

על-ידי pain_killer12
ב כללי

Featured Replies

פורסם

שלום חברים, קיבלתי בתרגיל בית שאלה די מסובכת

שצריך לפתור את נוסחת הנסיגה (להעביר לנוסחה רגילה שתלויה בn)

ואז למצוא לנוסחה הזאת חסם הדוק.

הנוסחה היא:

T(n) = T(0.13n) + T(0.87n) + 3n

הבעיה היא שאותנו לימדו גם בהרצאה וגם בתרגיל לפתור שאלות בסגנון Tn = T(n/x) + Fn

בלי משפט האב או משהו. פשוט אמרו לנו להמשיך לפתוח את הT הפנימי ואז "לנחש" פתרון

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

העניין הוא שלא הראו לנו דבר כזה וכמעט אף אחד לא הצליח.

תודה רבה מראש לעוזרים.

  • ציטוט
    • פורסם

    אם משרטטים את יחס הנסיגה כעץ בינארי, מקבלים משהו שנראה ככה:

    treeyn.jpg

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

    טענה: סכום הצמתים בכל רמה הוא (O(n

    הוכחה באינדוקציה:

    הטענה נכונה עבור השורש. נניח נכונות עבור הרמה הi.

    לכל צומת ברמה הi יש לכל היותר שני ילדים, ולכן סכום הצמתים ברמה הi+1 שווה לכל היותר לסכום הצמתים ברמה הi.

    טענה: עומק העץ הוא (O(logn

    הוכחה:

    העלה העמוק ביותר הוא העלה הימני ביותר. נסמן את עומקו ב-h

    3n*(0.87)^h = 1

    עבור n גדול מאוד h = logn

    משתי הטענות נובע שסכום הצמתים בכלל העץ הוא (O(nlogn, וזה (T(n

    עריכה: לגבי חסם תחתון נחכה לתשובה מעוד מישהו.

  • ציטוט

    • ארכיון

    דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.

    עבור לרשימת הדיונים

    דיונים חדשים

    Configure browser push notifications
    Chrome (Android)
    1. Tap the lock icon next to the address bar.
    2. Tap Permissions → Notifications.
    3. Adjust your preference.
    Chrome (Desktop)
    1. Click the padlock icon in the address bar.
    2. Select Site settings.
    3. Find Notifications and adjust your preference.