סיבוכית ריצה

[ruli yeret]

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

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

[yudsim]

O(n^4)

[ruli yeret]

o (n3) .1

o (n2) .2

o (n) .3

o (n log n) .4

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

[שניצל]

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

[ruli yeret]

fot i=1 to n

}

for j=1 to i

}

for k=1 to j

}

print k

while k<i

k=k^2

{

{

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

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

[doker]

O(n^2)...

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

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

[שניצל]

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

[ruli yeret]

תודה רבה!

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

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

[Sargon]

לפי דעתי זה 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, מעלים אותו בריבוע (אלא אם פותח הדיון כתב לא נכון את התרגיל).