שלום

קיבלנו את האלגוריתם הבא:

N הוא אורך הקלט

1. I=N

2.כל עוד I>=1 בצע:

2.1 סדרת משפטים שאינם משנים את ערכו של I

2.2עבור J מ-1 עד I בצע:

2.2.1 סדרת משפטים שאינם משנים את ערכיהם של I ו-J

2.3 I=I/2

צריכים למצוא את סיבוכיות האלגוריתם ופונקצית זמן הריצה

הלולאה שמתחילה בפקודה 2 ברורה ופשוטה - מתבצעת log2N פעמים

אבל הלולאה השנייה פחות ברור לי איך להגדיר

היא מתבצעת N+N/2 + N/4 + N/8 וכן הלאה, פעמים

תודה מראש

אם הבנתי נכון למה אתה מתכוון:

1. מתבצע בזמן קבוע ( O(1

2.

2.1 מתבצע בזמן קבוע.

2.2, מתבצעת I פעמים.

לכן כמו שאמרת מספר הפעולות בה הוא N+N/2 + N/4 + N/8... שזה חסום על ידי 2N.

לכן הסיבוכיות היא ( O(N

(יש עוד ( O(logN פעולות בגלל 2.1 אבל זה לא משנה את החסם של הסיבוכיות).

עריכה: לא חשוב הבנתי

תודה

לא. הלולאה מתבצעת logN פעמים, אבל אתה לא מבצע בכל פעם 2N פעולות.

בפעם הראשונה אתה מבצע N, בפעם השניה N/2 וכן הלאה. ולכן סה"כ 2N.

מספר האיברים בסדרה N, N/2, N/4 N/8... הוא logN וזה מספר הפעמים שהלולאה מתבצעת.

אגב קצת התבלבלתי מכל השיעורי בית האלה:

עכשיו שעזרת לי להגיע לתשובה(תודה קודם כל )

אז אומרים שפונקצית זמן הריצה היא:

log₂n + 2n+1

והסיבוכיות היא:

O(n)

?

שוב תודה

אם הכוונה בפונקצית זמן ריצה היא למספר הפעולות אז זה מה שכתבת, רק שצריך להכפיל את logN ו 2N במספר הפעולות הקבועות שיש בלולאות שלהם. (וזה גם לא מדויק כי 2N זה חסם, זה לא מספר הפעולות).

הסיבוכיות היא ( O(N.