(۱۹ اردیبهشت ۱۳۹۲ ۰۳:۲۲ ب.ظ)meiiika نوشته شده توسط:  الگوریتم زیر را در بهتربن و بدترین حالت محاسبه کنید
K=0
For i= 0 to n do
For j=1 to T[i] do
K=k+t[j]

[/code]
و مرتبه اجرایی این برنامه
Sum=0
FOR i=1 To N do
For j=1 to I*2 do
If(j mod i=0) then
For k :=1 to j do
Sum := Sum+1

واسه اولی نمیدونم T[i] چنده ولی احتمالا همون N^2 هست.

(۱۹ اردیبهشت ۱۳۹۲ ۰۳:۲۲ ب.ظ)meiiika نوشته شده توسط:  الگوریتم زیر را در بهتربن و بدترین حالت محاسبه کنید
K=0
For i= 0 to n do
For j=1 to T[i] do
K=k+t[j]

بهترین حالت زمانی هست که به ازای هر i، $T[i] = 0$ باشه. یعنی حلقه دومی اصلا اجرا نشه. در این صورت زمان اجرای کد برابر هست با حلقه اولی که میشه همون $\Theta(n)$ . بدترین حالت زمانی هست که برای هر i ، $T[i] = n$ باشه که در این صورت برای هر i، حلقه دومی از ۱ تا n تکرار میشه. در این صورت هزینه زمانی برابر هست با $\Theta(n^{2})$ .

سلام. برای سوال دوم شرط داخل حلقه دوم فقط به ازای j=i و j=2i برقراره. پس حلقه داخلی ۳ برابر مقدار هر i تکرار میشه. پیچیدگیش میشه $T(n)=3(1 2 3 ... n)\in \theta (n^2)$

خوب بازه ای برای T تعریف نشده. شاید تا n نباشه. احتمالاً یه چیزی از صورت سوال حذف شده. درضمن سوال اول مقدار رو میخاد نه پیچیدگی رو. هر بار مقدار [T[j رو به حاصل اضافه میکنه. با فرض اینکه تابع T یک جایگشت از اعداد ۰ تا n هست سوال رو حل میکنم. حلقه داخلی به اندازه مقدار تابع T تکرار میشه. یعنی از ۰ بار تا n بار با ترتیب نامشخص. حاصل k درنهایت برابر $\sum_{i=1}^n(n 1-i)T[i]$ میشه. (اولین مقدار از آرایه در تابع داخلی استفاده نمیشه.) پس در بیشترین حالت وقتیه که اعداد دنباله باشه $0,n,n-1,n-2,...,1$ و کمترین حالت میشه $n,0,1,2,3,...,n-1$. پس بیشترین حالت میشه $\sum_{i=1}^n(n 1-i)^2=\sum_{i=1}^ni^2$ و کمترین حالتش میشه $\sum_{i=1}^n(i-1)(n 1-i)=\sum_{i=0}^{n-1}i(n-i)$.