עבור לתוכן

עזרה בניתוח זמן ריצה

Featured Replies

פורסם

שלום,

אודה לעזרתכם בניתוח זמן הריצה של האלגוריתם המצורף כתמונה,

אני הגעתי לסיבוכיות של O(nlogn) אבל נראה שזה לא נכון

תודה

פורסם

זה אכן לא נכון.

אל תחשוב על הלולאה החיצונית והפנימית בנפרד - כלומר, אל תתן חסם על הלולאה החיצונית, חסם על הלולאה הפנימית, ותכפול ביניהם, כי יש קשר בין שתי הלולאות. תנסה לבנות ביטוי מתמטי מדויק שאומר כמה פעולות מתבצעות (כלומר בתכל'ס כמה איטרציות סה"כ יש ללולאה הפנימית) ותראה למה הביטוי הזה הופך. אם זה לא ברור לך, תנסה לקחת כמה n-ים לדוגמה ותראה מה יוצא לך.

פורסם
  • מחבר

תודה על התגובה...

משום מה אני לא מצליח לרדת לסוף דעתך...

פורסם

איזה ערכים מקבל i לאורך הריצה של הפונקציה?

לכל i, במשך כמה איטרציות רצה הלולאה הפנימית?

לכן, כמה איטרציות יש בסה"כ עבור הלולאה הפנימית?

ארכיון

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

דיונים חדשים