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 נכון?

כן.

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)

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

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

(5n-5) / n = k

נוסחא סופית.

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

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

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

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)

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

עזרה בבקשה.

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

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

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

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

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

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

K=0...

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

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

איזה שורש n?

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

a = 2 , B = 4

f(n) = nlogn

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

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

איזה ערך של K

יתן לך f(n)?

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