סיבוכיות אלגוריתם פשוט

[nadav245]

 S=0;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			for(k=1;k<=j;k++)
				S++;


	1. O(n^3)
	2. O(n^2)
	3. O(n^2 * logn)
	4. O(n)  

S משפט פשוט קבוע.

תשובה 1 נכון?

[Gil28]

כן.

[nadav245]

x = n; a = 0
	while(x > 1) {
		x= x - n/5;
		for(i=1;i<=x;i++) a++;
	}


1. O(n)
2. O(n^2)
3. O(n*logn)
4. O(1)

לא מצליח להבין איך ניגשים לזה בכלל

[Gil28]

תבדוק כמה פעמים מתבצעת כל לולאה (סדר גודל) ותכפיל את מה שיצא בכל לולאה מקוננת.

[nadav245]

(5n-5) / n = k

נוסחא סופית.

ליניארי נכון?

[Gil28]

הלולאה החיצונית מתבצעת 5 פעמים - מספר קבוע. הלולאה הפנימית רצה 4n/5 פעמים ועוד 3n/5 פעמים וכן הלאה.

סה"כ תקבל 2n בדיוק שזה (O(n.

[nadav245]

T(n) = 2T(n/4) + nlogn


1. Θ(n)
2. Θ(n · log2n)
3. Θ(n · logn)
4. Θ(n · √ n · log2n)

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

אף משפט אב מהצורה T(n) = aT(n/b) + f(n)

לא עונה על הצורה.

עזרה בבקשה.

[TheFly]

נראה שעושים לך תרגיל בית שקיבלת שאלה אחת כל פעם. :-\

[Gil28]

זה בדיוק משפט האב. תבדוק שוב.

[nadav245]

זה אמור להיות לפי מקרה ד של משפט האב אבל אני לא מוצא K שמגיע לשיויון.

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

אני אעריך כל עזרה שלכם.

[TheFly]

אם כך אז אני חוזר בי. בהצלחה.

[Gil28]

K=0...

[nadav245]

לוג בחזקת 0 זה 1

אז איך שורש N יוצא לך N לוג N?

[Gil28]

איזה שורש n?

אם (f(n)= Θ(n^log_b^a· log^kn עבור k>=0, אז (T(n)= Θ(n^log_b^a· log^k+1n.

[nadav245]

a = 2 , B = 4

f(n) = nlogn

n^log_b^{a = שורש N}

Θ(n^log_b^a· log^kn)

איזה ערך של K

יתן לך f(n)?

אני לא חושב שזה 0