الگوریتم زیر را در بهتربن و بدترین حالت محاسبه کنید
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
(۱۹ اردیبهشت ۱۳۹۲ ۰۳:۲۲ ب.ظ)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 هست.
سلام. برای سوال دوم شرط داخل حلقه دوم فقط به ازای j=i و j=2i برقراره. پس حلقه داخلی ۳ برابر مقدار هر i تکرار میشه. پیچیدگیش میشه [tex]T(n)=3(1 2 3 ... n)\in \theta (n^2)[/tex]
(۱۹ اردیبهشت ۱۳۹۲ ۰۳:۲۲ ب.ظ)meiiika نوشته شده توسط: الگوریتم زیر را در بهتربن و بدترین حالت محاسبه کنید
K=0
For i= 0 to n do
For j=1 to T[i] do
K=k+t[j]
بهترین حالت زمانی هست که به ازای هر i، [tex]T[i] = 0[/tex] باشه. یعنی حلقه دومی اصلا اجرا نشه. در این صورت زمان اجرای کد برابر هست با حلقه اولی که میشه همون [tex]\Theta(n)[/tex] . بدترین حالت زمانی هست که برای هر i ، [tex]T[i] = n[/tex] باشه که در این صورت برای هر i، حلقه دومی از ۱ تا n تکرار میشه. در این صورت هزینه زمانی برابر هست با [tex]\Theta(n^{2})[/tex] .
خوب بازه ای برای T تعریف نشده. شاید تا n نباشه. احتمالاً یه چیزی از صورت سوال حذف شده. درضمن سوال اول مقدار رو میخاد نه پیچیدگی رو. هر بار مقدار [T[j رو به حاصل اضافه میکنه. با فرض اینکه تابع T یک جایگشت از اعداد ۰ تا n هست سوال رو حل میکنم. حلقه داخلی به اندازه مقدار تابع T تکرار میشه. یعنی از ۰ بار تا n بار با ترتیب نامشخص. حاصل k درنهایت برابر [tex]\sum_{i=1}^n(n 1-i)T[i][/tex] میشه. (اولین مقدار از آرایه در تابع داخلی استفاده نمیشه.) پس در بیشترین حالت وقتیه که اعداد دنباله باشه [tex]0,n,n-1,n-2,...,1[/tex] و کمترین حالت میشه [tex]n,0,1,2,3,...,n-1[/tex]. پس بیشترین حالت میشه [tex]\sum_{i=1}^n(n 1-i)^2=\sum_{i=1}^ni^2[/tex] و کمترین حالتش میشه [tex]\sum_{i=1}^n(i-1)(n 1-i)=\sum_{i=0}^{n-1}i(n-i)[/tex].