۰
subtitle
ارسال: #۱
  
مرتبه های زمانی
سلام
ببخشید می شه مرتبه های زمانی مثال های زیر را برایم توضیح دهید ( با نماد های مجانبی)
[tex]T(n)=5T(n/5) {\frac{n}{logn}}[/tex]
T(n)=T(n/2)+T(n/8)+T(n/4)+n
T(n)=T(n-1)+1/n
T(n)=T(n-1)+log n
T(n)=n^1/2 T (n^1/2) + n
ما قضیه اصلی را خوندیم که به شکل aT(n/b) +f(n) a بود یا آنهایی که به شکل aT(n-b) +c
اینها را چه جوری حل کنیم؟
من خیلی توی اینا مشکل دارم
ببخشید می شه مرتبه های زمانی مثال های زیر را برایم توضیح دهید ( با نماد های مجانبی)
[tex]T(n)=5T(n/5) {\frac{n}{logn}}[/tex]
T(n)=T(n/2)+T(n/8)+T(n/4)+n
T(n)=T(n-1)+1/n
T(n)=T(n-1)+log n
T(n)=n^1/2 T (n^1/2) + n
ما قضیه اصلی را خوندیم که به شکل aT(n/b) +f(n) a بود یا آنهایی که به شکل aT(n-b) +c
اینها را چه جوری حل کنیم؟
من خیلی توی اینا مشکل دارم
۰
ارسال: #۲
  
مرتبه های زمانی
وقتی توان log منفی هستش فک کنم فقط از طریق درخت بازگشتی حل بشه!
۰
ارسال: #۳
  
RE: مرتبه های زمانی
(۰۴ بهمن ۱۳۹۱ ۰۵:۲۲ ب.ظ)zfmo نوشته شده توسط: سلام
ببخشید می شه مرتبه های زمانی مثال های زیر را برایم توضیح دهید ( با نماد های مجانبی)
[tex]T(n)=5T(n/5) {\frac{n}{logn}}[/tex]
T(n)=T(n/2)+T(n/8)+T(n/4)+n
T(n)=T(n-1)+1/n
T(n)=T(n-1)+log n
T(n)=n^1/2 T (n^1/2) + n
ما قضیه اصلی را خوندیم که به شکل aT(n/b) +f(n) a بود یا آنهایی که به شکل aT(n-b) +c
اینها را چه جوری حل کنیم؟
من خیلی توی اینا مشکل دارم
سلام [/align]
برای اولی تغییر متغییر بده به ۵ به توان k و حلش کن فکر کنم بشه n * log(logn)
دومی رو : تغییر متغییر بده به ۲ به توان k و حل کن
سومی : بازش کن می شه جمع ۱ تا ۱/n که می شه logn
چهارمی : بازش کن می شه جمع log 1 تا log (n) که میشه لگاریتم n فاکتوریل و تقریبا nlogn
پنجمی : تغییر متغییر به ۲ به توان k
ارسال: #۴
  
RE: مرتبه های زمانی
quote='ana_12345' pid='155851' dateline='1358958069']
برای اولی تغییر متغییر بده به ۵ به توان k و حلش کن فکر کنم بشه n * log(logn)
[/quote]
من با این تغییر متغیر شما نتونستم حلش کنم اگه میشه بیشتر توضیح بدید.
ولی با جوابتون موافقم!
برای اولی تغییر متغییر بده به ۵ به توان k و حلش کن فکر کنم بشه n * log(logn)
[/quote]
من با این تغییر متغیر شما نتونستم حلش کنم اگه میشه بیشتر توضیح بدید.
ولی با جوابتون موافقم!
(۱۳ بهمن ۱۳۹۱ ۰۵:۲۶ ب.ظ)csharpisatechnology نوشته شده توسط: [tex]5^2T(n/5^2) 5(\frac{n}{5*lg(\frac{n}{5})}) \frac{n}{lgn}\sim eq h*o(n)=o(nlgn)[/tex]به نظرم این حل درست نیست!
ارسال: #۵
  
RE: مرتبه های زمانی
(۰۴ بهمن ۱۳۹۱ ۰۸:۵۱ ب.ظ)ana_12345 نوشته شده توسط:(04 بهمن ۱۳۹۱ ۰۵:۲۲ ب.ظ)zfmo نوشته شده توسط: سلام
ببخشید می شه مرتبه های زمانی مثال های زیر را برایم توضیح دهید ( با نماد های مجانبی)
[tex]T(n)=5T(n/5) {\frac{n}{logn}}[/tex]
T(n)=T(n/2)+T(n/8)+T(n/4)+n
T(n)=T(n-1)+1/n
T(n)=T(n-1)+log n
T(n)=n^1/2 T (n^1/2) + n
ما قضیه اصلی را خوندیم که به شکل aT(n/b) +f(n) a بود یا آنهایی که به شکل aT(n-b) +c
اینها را چه جوری حل کنیم؟
من خیلی توی اینا مشکل دارم
سلام [/align]
برای اولی تغییر متغییر بده به ۵ به توان k و حلش کن فکر کنم بشه n * log(logn)
دومی رو : تغییر متغییر بده به ۲ به توان k و حل کن
سومی : بازش کن می شه جمع ۱ تا ۱/n که می شه logn
چهارمی : بازش کن می شه جمع log 1 تا log (n) که میشه لگاریتم n فاکتوریل و تقریبا nlogn
پنجمی : تغییر متغییر به ۲ به توان k
سلام، من تلاش کردم T(n)=T(n/2)+T(n/8)+T(n/4)+n رو با تغییر متغیر حل کنم ولی موفق نشدم. بعد از تغییر متغیر رابطه تبدیل به شکل زیر میشه:
[tex]n=2^k[/tex]
[tex]T(2^k) = T(2^{k-1}) T(2^{k-2}) T(2^{k-3}) 2^k[/tex]
[tex]F(k) = T(2^k) => F(k) = F(k-1) F(k-2) F(k-3) 2^k[/tex]
در اصل من توی حل کردن این رابطهی آخری مشکل داشتم. سعی کردم با تکرار حلش کنم که به جای خوبی نرسیدم. ممنون میشم کمک کنید.
۰
ارسال: #۶
  
مرتبه های زمانی
سمت چپ میشه teta_n
اما سمت راست میشه nlg^{-1}n
چون توان از ۰ کمتر شد با master نمیشه حلش کرد.
اما سمت راست میشه nlg^{-1}n
چون توان از ۰ کمتر شد با master نمیشه حلش کرد.
۰
ارسال: #۷
  
مرتبه های زمانی
فکر کنم با درخت تصمیم میشه این:
[tex]5^2T(n/5^2) 5(\frac{n}{5*lg(\frac{n}{5})}) \frac{n}{lgn}\sim eq h*o(n)=o(nlgn)[/tex]
رابطه ی فوق به اندازه ی o(n) رشد می کنه و ارتفاع درخت میشه lgn
شایدم به توان لگاریم یکی باید اضاف بشه یا کلا جواب همون ارتفاع درخت یا lgn میشه شک دارم
[tex]5^2T(n/5^2) 5(\frac{n}{5*lg(\frac{n}{5})}) \frac{n}{lgn}\sim eq h*o(n)=o(nlgn)[/tex]
رابطه ی فوق به اندازه ی o(n) رشد می کنه و ارتفاع درخت میشه lgn
شایدم به توان لگاریم یکی باید اضاف بشه یا کلا جواب همون ارتفاع درخت یا lgn میشه شک دارم
۰
۰
ارسال: #۹
  
مرتبه های زمانی
موضوعهای مرتبط با این موضوع... |
|||||
موضوع: | نویسنده | پاسخ: | بازدید: | آخرین ارسال | |
سلام لطفاً یکی به من بگه مرتبه زمانی ها چطوری به log تبدیل میشن فرمول داره؟؟ | Azadam | ۶ | ۵,۰۴۹ |
۰۶ دى ۱۴۰۰ ۰۹:۰۲ ق.ظ آخرین ارسال: Soldier's life |
|
مرتبه ایجاد درخت | rad.bahar | ۱ | ۳,۴۱۹ |
۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ آخرین ارسال: rad.bahar |
|
مرتبه شبه کد | rad.bahar | ۱ | ۲,۳۷۵ |
۲۲ مهر ۱۳۹۹ ۰۹:۳۲ ب.ظ آخرین ارسال: BBumir |
|
حل مساله مرتبه زمانی حلقه های تو در تو | sarashahi | ۱۶ | ۲۳,۲۷۹ |
۱۹ خرداد ۱۳۹۹ ۰۱:۱۶ ب.ظ آخرین ارسال: gillda |
|
مرتبه زمانی | Sanazzz | ۱۷ | ۲۱,۸۳۴ |
۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۶ ب.ظ آخرین ارسال: mohsentafresh |
|
پیچیدگی زمانی اکشن های قابل اعمال در یک وضعیت | اsepid8994 | ۰ | ۱,۸۲۰ |
۲۹ اسفند ۱۳۹۸ ۱۲:۵۱ ب.ظ آخرین ارسال: اsepid8994 |
|
مرتبه زمانی یافتن قطر | Sepideh96 | ۲ | ۳,۸۵۷ |
۰۸ آذر ۱۳۹۸ ۰۴:۳۴ ب.ظ آخرین ارسال: erfan30 |
|
مرتبه مانی | Sanazzz | ۳ | ۳,۷۷۳ |
۰۵ خرداد ۱۳۹۸ ۰۲:۳۶ ب.ظ آخرین ارسال: Sanazzz |
|
یافتن دو عدد پیچیدگی زمانی O(n) | porseshgar | ۲ | ۳,۹۸۱ |
۱۵ بهمن ۱۳۹۷ ۱۲:۱۶ ب.ظ آخرین ارسال: porseshgar |
|
مرتبه زمانی | Sanazzz | ۰ | ۲,۰۶۷ |
۰۴ بهمن ۱۳۹۷ ۰۵:۴۱ ب.ظ آخرین ارسال: Sanazzz |
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close