שלום,

אני צריך לבנות בשפת 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 אולי?

http://he.wikipedia.org/wiki/%D7%9E%D7%99%D7%95%D7%9F_(%D7%9E%D7%93%D7%A2%D7%99_%D7%94%D7%9E%D7%97%D7%A9%D7%91)

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

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

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

הועבר לתכנות כללי.