public static void f(int n)
{
  for (int i=n; i>0; i--)
  {
  int j = n;
  while (j>0)
  j = j/4;
  }
}

זה נראה כאילו ה-while זו לולאה אינסופית את המספר הוא חיובי

חילוק של int הוא מעוגל למטה, אז j כן יגיע ל-0 לאחר מספר מסויים של איטרציות.

אם לא היה ה-while הסיבוכיות הייתה O של n.

מה קורה בגלל ה-while ? האם עדיין נשאר n ?

תחשוב כמה פעמים צריך לחלק מספר ב-4 בשביל להגיע ל-0. רמז עבה: יש פה log.

לדוגמא לוגריתם log_2(32) = x שואל 2 בחזקת מה שווה 32. התשובה x=5. אז אתה ש- 32 שווה 2 בחזקת 5. ואם את 2 בחזקת 5 אתה מחלק ב-2 אתה מקבל 2 בחזקת 4. אז כמה פעמים תצתרך לחלק כדי להגיע ל-0?

וכמה פעמים אתה צריך לחלק מספר ב-4 בשביל להגיע ל-0?

אוקיי תודה רבה אבל השאלה שלי היא האם ה-while משפיע על הסיבוכיות שבלעדיו יש לי סיבוכיות n או שאני אמור להתחשב גם ב- while ?

וואו יצאתי דביל, כמו שנאמר לך יש לך פה n מהfor וlogn מהwhile, סהכ nlogn

Moon-Mage: מה?

עריכה: האינדנטציה של הקוד לא נכונה אז באמת אפשר לפספס...

ואני אוסיף כי כבר ענית: צריך לשים לב באיזה בסיס ה-log.

wow: הסיבוכיות של ה-while היא לא O(1) וכמובן שהיא משנה.

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

Moon-Mage: מה?

wow: הסיבוכיות של ה-while היא לא O(1) וכמובן שהיא משנה.

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

עזוב לא ראיתי את הwhile שקראתי את ההודעה הראשונה