פורסם 2011 בינואר 1414 שנים שלום,אני צריך לבנות בשפת C תוכנית עם סיבוכיות זמן O(n+k)מה האפשרויות?לולאה מקסימלית של n ועוד k?אם אני עושה לולאה מקוננת n*k , האם זה מסדר גודל הנדרש?תודה.
פורסם 2011 בינואר 1414 שנים שים לב ש- K לא יכול להיות מספר קבוע.אתה יכול לעשות 2 לולאות אחת אחרי השניה, שהראשונה רצה N פעמים, והשניה רצה K פעמים.
פורסם 2011 בינואר 1514 שנים שים לב ש- K לא יכול להיות מספר קבוע.אתה יכול לעשות 2 מספר קבוע כלשהו של לולאות אחת אחרי השניה, שהראשונה רצה N פעמים, והשניה רצה K פעמים.
פורסם 2011 בינואר 1514 שנים 2 לולאות אחת אחרי השניה = חיבור.מה שחשוב זה כמה זמן 2 הלולאות רצות.הראשונה רצה N, והשניה רצה K, ולכן שתיהן יחד רצות N+K.המספר הקבוע לא מתייחס למספר הלולאות, אלא לכמה איטרציות בלולאה.נרחיב את הדוגמא, ונרצה שזמן הריצה יהיה O(m+n+k). דוגמא לזמן ריצה שכזה הוא 3 לולאות, שהראשונה רצה N, השניה M והשלישות K.אם מספר הלולאות לא יהיה קבוע, אז זה בעצם כמו לולאה בתוך לולאה. בהנחה והלולאה החיצונית רצה N והפנימית רצה K איטרציות, זמן הריצה יהיה - O(K + K + ... + K) = O(N * K) N פעמים
פורסם 2011 בינואר 1514 שנים 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)
פורסם 2011 בינואר 1614 שנים bucket sort עובד בסיבוכיות n+k , אבל k בנוסחה הוא האיבר הגדול ביותר עבור רצף מספרים 1 עד k.לכן לרוב הדברים אלגוריתם המיון הזה לא יעיל במיוחד.
פורסם 2011 בינואר 1614 שנים אתה יכול לכתוב תוכנית שמבצעת סריקת DFS על גרף,סיבוכיות DFS במקרה הגרוע O(E+V)
ארכיון
דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.