۰
subtitle
ارسال: #۱
  
سوال مرتبه اجرایی
الگوریتم زیر را در بهتربن و بدترین حالت محاسبه کنید
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
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
۰
ارسال: #۲
  
RE: سوال مرتبه اجرایی
(۱۹ اردیبهشت ۱۳۹۲ ۰۳:۲۲ ب.ظ)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 هست.
ارسال: #۳
  
RE: سوال مرتبه اجرایی
(۱۹ اردیبهشت ۱۳۹۲ ۰۳:۲۲ ب.ظ)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] .
۰
ارسال: #۴
  
سوال مرتبه اجرایی
سلام. برای سوال دوم شرط داخل حلقه دوم فقط به ازای j=i و j=2i برقراره. پس حلقه داخلی ۳ برابر مقدار هر i تکرار میشه. پیچیدگیش میشه [tex]T(n)=3(1 2 3 ... n)\in \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].
موضوعهای مرتبط با این موضوع... |
|||||
موضوع: | نویسنده | پاسخ: | بازدید: | آخرین ارسال | |
سلام لطفاً یکی به من بگه مرتبه زمانی ها چطوری به log تبدیل میشن فرمول داره؟؟ | Azadam | ۶ | ۵,۰۴۴ |
۰۶ دى ۱۴۰۰ ۰۹:۰۲ ق.ظ آخرین ارسال: Soldier's life |
|
مرتبه ایجاد درخت | rad.bahar | ۱ | ۳,۴۱۶ |
۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ آخرین ارسال: rad.bahar |
|
مرتبه شبه کد | rad.bahar | ۱ | ۲,۳۷۳ |
۲۲ مهر ۱۳۹۹ ۰۹:۳۲ ب.ظ آخرین ارسال: BBumir |
|
حل مساله مرتبه زمانی حلقه های تو در تو | sarashahi | ۱۶ | ۲۳,۲۷۰ |
۱۹ خرداد ۱۳۹۹ ۰۱:۱۶ ب.ظ آخرین ارسال: gillda |
|
مرتبه زمانی | Sanazzz | ۱۷ | ۲۱,۸۲۰ |
۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۶ ب.ظ آخرین ارسال: mohsentafresh |
|
مرتبه زمانی یافتن قطر | Sepideh96 | ۲ | ۳,۸۵۲ |
۰۸ آذر ۱۳۹۸ ۰۴:۳۴ ب.ظ آخرین ارسال: erfan30 |
|
مرتبه مانی | Sanazzz | ۳ | ۳,۷۷۱ |
۰۵ خرداد ۱۳۹۸ ۰۲:۳۶ ب.ظ آخرین ارسال: Sanazzz |
|
مرتبه زمانی | Sanazzz | ۰ | ۲,۰۶۵ |
۰۴ بهمن ۱۳۹۷ ۰۵:۴۱ ب.ظ آخرین ارسال: Sanazzz |
|
مشکل در محاسبه مرتبه ایک سوال | Mr.R3ZA | ۰ | ۱,۹۰۱ |
۲۴ خرداد ۱۳۹۷ ۰۱:۰۳ ب.ظ آخرین ارسال: Mr.R3ZA |
|
پنجمین ازمون استخدام مشترک فراگیر دستگاه های اجرایی کشور | naghmeh70 | ۷ | ۷,۷۴۹ |
۳۱ اردیبهشت ۱۳۹۷ ۱۱:۳۵ ب.ظ آخرین ارسال: αɾια |
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close