מה הסיבוכית ריצה של האלגוריתם

for i=1 to n { for j = 1 to i { for k = 1 to j print k k = 2 while k < i k = k2 } }

O(n^4)

o (n3) .1

o (n2) .2

o (n) .3

o (n log n) .4

זה התשובות האפשריות לתרגיל הנ"ל תשובתך אינה מופיעה באפרויות

יעזור אם תדביק את הקוד בצורה מסודרת, ולא בשורה אחת. עדיף גם להשתמש בטג קוד (במצב עריכה מתקדם, כפתור עם ציור #). הקוד לא ממש קריא ככה.

fot i=1 to n

}

for j=1 to i

}

for k=1 to j

}

print k

while k<i

k=k^2

{

{

- - - תגובה אוחדה: - - -

מקווה שעכשיו יותר קריא תודה מראש!

O(n^2)...

אני דיי בטוח..

האמת פסלתי את כל התשובות האחרות וככה הגעתי.

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

תודה רבה!

- - - תגובה אוחדה: - - -

שפת התיכנות שאני משתמש בה היא C

לפי דעתי זה O(n^3)

הקטע המסובך זה לעשות

{ for i = 1 to n { k = 2 while k < i k = k*2

אם נסתכל על

k = 2 while k < i k = k*2

הריי שזה

O(log(i)) Complexity

אבל, i בעצמו רץ על 1 עד n

כלומר יש לנו פה סכום של הלוגים מ1 עד n.

לפי דעתי צריך להראות שהסכום של הלוגים מ1 עד n שקול בעצם ל O(n) Complexity

ואז משתי הלולאות האחרות שסתם מכפילות לך את הסכום הנ"ל ב n*n/4 יצא לך שהסיבוכיות הסופית היא

O(n^3) Complexity

יש לך טעות קטנה: לא מכפילים את k ב-2, מעלים אותו בריבוע (אלא אם פותח הדיון כתב לא נכון את התרגיל).