עבור לתוכן
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.

סיבוכיות זמן

על-ידי wtcher
ב תכנות

Featured Replies

פורסם

שלום,

אני צריך לבנות בשפת C תוכנית עם סיבוכיות זמן O(n+k)

מה האפשרויות?

לולאה מקסימלית של n ועוד k?

אם אני עושה לולאה מקוננת n*k , האם זה מסדר גודל הנדרש?

תודה.

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

    שים לב ש- K לא יכול להיות מספר קבוע.

    אתה יכול לעשות 2 לולאות אחת אחרי השניה, שהראשונה רצה N פעמים, והשניה רצה K פעמים.

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

    שים לב ש- K לא יכול להיות מספר קבוע.

    אתה יכול לעשות 2 מספר קבוע כלשהו של לולאות אחת אחרי השניה, שהראשונה רצה N פעמים, והשניה רצה K פעמים.

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

    2 לולאות אחת אחרי השניה = חיבור.

    מה שחשוב זה כמה זמן 2 הלולאות רצות.

    הראשונה רצה N, והשניה רצה K, ולכן שתיהן יחד רצות N+K.

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

    נרחיב את הדוגמא, ונרצה שזמן הריצה יהיה O(m+n+k). דוגמא לזמן ריצה שכזה הוא 3 לולאות, שהראשונה רצה N, השניה M והשלישות K.

    אם מספר הלולאות לא יהיה קבוע, אז זה בעצם כמו לולאה בתוך לולאה. בהנחה והלולאה החיצונית רצה N והפנימית רצה K איטרציות, זמן הריצה יהיה - 


    O(K + K + ... + K) = O(N * K)
       N פעמים

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

    אין איזשהו מיון שרת על (O(N+K? Counting Sort אולי?

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

    bucket sort עובד בסיבוכיות n+k , אבל k בנוסחה הוא האיבר הגדול ביותר עבור רצף מספרים 1 עד k.

    לכן לרוב הדברים אלגוריתם המיון הזה לא יעיל במיוחד.

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

    אתה יכול לכתוב תוכנית שמבצעת סריקת DFS על גרף,סיבוכיות DFS במקרה הגרוע O(E+V)

  • ציטוט

    • ארכיון

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

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

    דיונים חדשים

    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.