زمان کنونی: ۲۲ آبان ۱۴۰۳, ۱۲:۱۹ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

[نکات] کارآیی ، تحلیل و مرتبه الگوریتم ها - روابط بازگشتی

ارسال:
  

Masoud05 پرسیده:

[نکات] کارآیی‌، تحلیل و مرتبه الگوریتم‌ها - روابط بازگشتی

برای شروع:
نکته:
n^2+log n از مرتبه تتا n^2هست اماn^2*logn نه

۲
ارسال:
  

mfXpert پاسخ داده:

RE: [نکات] کارآیی‌، تحلیل و مرتبه الگوریتم‌ها - روابط بازگشتی

جواب هر رابطه بازگشتی به فرم [tex]T(n)=T(\alpha n) T((1-\alpha) n) \Theta (n)[/tex] به طوری که [tex]\alpha[/tex] یک عدد ثابت و در محدوده [tex]0<\alpha <1[/tex] است برابر است با [tex]T(n)=\Theta (nlgn)[/tex]
خیلی راحت میشه با درخت بازگشتی اثباتش کرد

۰
ارسال:
  

۵۴m4n3h پاسخ داده:

RE: [نکات] کارآیی‌، تحلیل و مرتبه الگوریتم‌ها - روابط بازگشتی

[تصویر:  attachment.php?aid=115]

یکی از تمرین های CLRS هست که توی کتاب یوسفی جوابش بود، به نظرم خیلی مفیده!


فایل‌(های) پیوست شده

۱
ارسال:
  

۵۴m4n3h پاسخ داده:

RE: [نکات] کارآیی‌، تحلیل و مرتبه الگوریتم‌ها - روابط بازگشتی

[تصویر:  gif.download?T(n)=T(n-m)+g(n)&amp;sp...pace;g(n))]

[تصویر:  m})]

g = چند جمله ای

۱
ارسال:
  

ف.ش پاسخ داده:

RE: [نکات] کارآیی‌، تحلیل و مرتبه الگوریتم‌ها - روابط بازگشتی

[tex]n^{k}=O((logn)^{logn})[/tex]

این رو یکجا خوندم ولی دلیلش رو نمیدونم اما فکر کنم عدد بگذارید دلیلش رو بفهمید!

ارسال:
  

۵۴m4n3h پاسخ داده:

RE: [نکات] کارآیی‌، تحلیل و مرتبه الگوریتم‌ها - روابط بازگشتی

(۱۴ بهمن ۱۳۸۹ ۰۸:۵۵ ب.ظ)afagh1389 نوشته شده توسط:  [tex]n^{k}=O((logn)^{logn})[/tex]

این رو یکجا خوندم ولی دلیلش رو نمیدونم اما فکر کنم عدد بگذارید دلیلش رو بفهمید!

با توجه به این نکته که‌: [tex]{\color{red} a}^{\log {\color{blue}b}}={\color{blue} b}^{\log {\color{red} a}}[/tex]


[tex]{\color{red} \log n}^{\log {\color{blue} n}}={\color{blue} n}^{\log {\color{red} \log n}}[/tex]
یافتن تمامی ارسال‌های این کاربر

۱
ارسال:
  

amino22 پاسخ داده:

[نکات] کارآیی‌، تحلیل و مرتبه الگوریتم‌ها - روابط بازگشتی

T(n)=2T(n/2)+nlogn
به عقیده من فرآیند جواب به این صورت میشه:
T(n/2)+T(n/2)+nlogn
پس در نهایت داریم:
n+nlogn
که میشه خود (O(nlogn

ارسال:
  

Masoud05 پاسخ داده:

RE: [نکات] کارآیی‌، تحلیل و مرتبه الگوریتم‌ها - روابط بازگشتی

(۱۷ بهمن ۱۳۹۰ ۱۰:۲۳ ب.ظ)amino22 نوشته شده توسط:  
(03 آذر ۱۳۹۰ ۱۱:۵۹ ق.ظ)mar236 نوشته شده توسط:  
T(n)=2T(n/2)+nlogn
به عقیده من فرآیند جواب به این صورت میشه:
T(n/2)+T(n/2)+nlogn
پس در نهایت داریم:
n+nlogn
که میشه خود (O(nlogn
نه روند کار غلطه‌، روند صحیح در بالا بچه‌ها توضیح دادن.
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

ف.ش پاسخ داده:

RE: نکات طراحی الگوریتم

[tex]T(n)=T(n-1) T(n-1)=2*T(n-1)\epsilon O(2^{n})[/tex]


که توی کتاب مقسمی اشتباها دومی رو از مرتبه (O(n گرفته!!!!

۰
ارسال: #۱۰
  

Masoud05 پاسخ داده:

RE: [نکات] پیچیدگی زمانی

برای حل رابطه بازگشتی از طریق درخت بازگشت به این نکته دقت کنید:
ارتفاع درخت (h) توسط فرمول

محاسبه میشود که در آن b اندازه زیر مسائل است.
یادآوری:
[تصویر:  attachment.php?aid=97]

۰
ارسال: #۱۱
  

Masoud05 پاسخ داده:

RE: [نکات] کارآیی‌، تحلیل و مرتبه الگوریتم‌ها - روابط بازگشتی

به نکته ظریف زیر دقت کنید:
[تصویر:  attachment.php?aid=119]
------------------


بچه‌ها شما هم شرکت کنید دیگهBig Grin

۰
ارسال: #۱۲
  

Masoud05 پاسخ داده:

RE: [نکات] کارآیی‌، تحلیل و مرتبه الگوریتم‌ها - روابط بازگشتی

یه نکته جالب برای حل روابط بازگشتی:
[تصویر:  attachment.php?aid=135]


[تصویر:  attachment.php?aid=136]


فایل‌(های) پیوست شده

۰
ارسال: #۱۳
  

Masoud05 پاسخ داده:

RE: [نکات] کارآیی‌، تحلیل و مرتبه الگوریتم‌ها - روابط بازگشتی

[تصویر:  attachment.php?aid=153]

تذکر‌: در این نکته o کوچک داریم. هر چند که برای O بزرگ هم صحیح هست . اما با o کوچک به این نکته پی میبریم که مقدار سمت چپ عبارت اکیداً کوچکتر هست.

۰
ارسال: #۱۴
  

Masoud05 پاسخ داده:

RE: [نکات] کارآیی‌، تحلیل و مرتبه الگوریتم‌ها - روابط بازگشتی

با سلا م به دوستان‌، یه فایل upload براتون کردم که سوالات دانشگاه MIT هست جواب هم کنارش هست . خیلی فوق العاده هست . حتماً حتماً حتماً دانلود کنید


مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

۰
ارسال: #۱۵
  

Masoud05 پاسخ داده:

RE: [نکات] کارآیی‌، تحلیل و مرتبه الگوریتم‌ها - روابط بازگشتی

سلام . یه سوال جالب از جزوه سید جوادی( اگه بتونم نکات جالبش رو براتون میزارم)
برای ۴ خانه در نظر بگیرید جواب میشه ۱۳ .چرا؟ فرض کنید ۴ بیت داریم (۴ خانه) که هر یک ۲ مقدار می تواند داشته باشد پس ۴ ^۲= ۱۶ حالت داریم اما ۳ حالت غیر مجاز داریم( ۴ خانه سفید - ۳ خانه اول سفید - ۳ خانه آخر سفید) پس ۳-۱۶ تعداد کل حالات میشه
میتونید با رابطه بازگشتی داده شده اینو رو نشان بدین

[تصویر:  attachment.php?aid=2658]


فایل‌(های) پیوست شده


۰
ارسال: #۱۶
  

sepid پاسخ داده:

[نکات] کارآیی‌، تحلیل و مرتبه الگوریتم‌ها - روابط بازگشتی

نکته در مورد قضیه اصلی:
در بعضی موارد نمی توان از قضیه اصلی استفاده کرد مانند مثال های زیر:
۱) T(n)=2T(n/2)+nlogn
T(n)=2T(n/2)+n/logn(2
زیرا در مورد ۱ علیرغم اینکه با استفاده از قضیه اصلی n=O(nlognولی چون به صورت چندجمله ای بزرگتر نیست پس نمی توان از قضیه اصلی استفاده کرد.
در مورد ۲ هم n/logn=O(n ولی حاصل تقسیم تابع بزرگتر بر کوچکتر چند جمله ای نیست پس از این قضیه نمی توان استفاده کرد .
منبع: صفحه ۹۸CLRS
مشاهده‌ی وب‌سایت کاربر

۰
ارسال: #۱۷
  

nmusavi پاسخ داده:

[نکات] کارآیی‌، تحلیل و مرتبه الگوریتم‌ها - روابط بازگشتی

(۱۴ آبان ۱۳۹۰ ۱۲:۲۶ ق.ظ)mojgan نوشته شده توسط:  
(21 آذر ۱۳۸۹ ۰۱:۵۶ ب.ظ)Masoud05 نوشته شده توسط:  با سلا م به دوستان‌، یه فایل upload براتون کردم که سوالات دانشگاه MIT هست جواب هم کنارش هست . خیلی فوق العاده هست . حتماً حتماً حتماً دانلود کنید


مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

سلام
مرسی از این همه همت
من نتونستم این رو دانلود کنم
دقیقا رو کدو گزینه برم
چون هر جا کلیلک می کنم یا صفحه‌ی دیگه باز می شه یا با پسوند اچ تی‌ام ال ذخیره می شه
ممنون
in quiz haye danesh gahe mit too site khode daneshgah hast berid az oonja download konid

۰
ارسال: #۱۸
  

fatima2007 پاسخ داده:

[نکات] کارآیی‌، تحلیل و مرتبه الگوریتم‌ها - روابط بازگشتی

سلام
من یه سوال دارم؟؟؟؟؟
سوال ۸۹ ای تی:

۴f(n/2)+n^2logn

به نظر من میشه n^2logn ولی جواب زده n^2 (log〖n)〗^۲
من کتوجه نمی شم چرا مکه k همون ۲ نیست پس باید بگیم b^k=a و جواب میشه n^2logn ؟؟
ممکنه کسی کمک کنه؟؟

۰
ارسال: #۱۹
  

fa_karoon پاسخ داده:

[نکات] کارآیی ، تحلیل و مرتبه الگوریتم ها - روابط بازگشتی

(۰۳ آذر ۱۳۸۹ ۱۲:۴۱ ق.ظ)۵۴m4n3h نوشته شده توسط:  [تصویر:  attachment.php?aid=115]

یکی از تمرین های CLRS هست که توی کتاب یوسفی جوابش بود، به نظرم خیلی مفیده!
آیا منظور همان ترتیب مرتبه زمانی (بیگ او) این توابع است؟
می شه سوال رو بنویسید؟
مشاهده‌ی وب‌سایت کاربر

ارسال: #۲۰
  

Masoud05 پاسخ داده:

RE: [نکات] کارآیی ، تحلیل و مرتبه الگوریتم ها - روابط بازگشتی

(۱۶ فروردین ۱۳۹۱ ۰۱:۱۵ ق.ظ)fa_karoon نوشته شده توسط:  آیا منظور همان ترتیب مرتبه زمانی (بیگ او) این توابع است؟
می شه سوال رو بنویسید؟

علامت کوچکتر که گذاشته یعنی small o پس قطعا برای Big O هم درسته .
یافتن تمامی ارسال‌های این کاربر



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  جزوه خلاصه نکات مهم فصول ابتدایی درس مهندسی نرم افزار Happiness.72 ۱ ۳,۸۱۵ ۱۳ خرداد ۱۴۰۱ ۰۶:۲۸ ب.ظ
آخرین ارسال: M o h m m @ d
  استخدام کارشناس تحلیل داده zeinab_IT ۰ ۱,۲۶۹ ۱۷ بهمن ۱۴۰۰ ۱۲:۳۱ ب.ظ
آخرین ارسال: zeinab_IT
Exclamation سلام لطفاً یکی به من بگه مرتبه زمانی ها چطوری به log تبدیل میشن فرمول داره؟؟ Azadam ۶ ۴,۸۳۴ ۰۶ دى ۱۴۰۰ ۰۹:۰۲ ق.ظ
آخرین ارسال: Soldier's life
  بهترین گرایش برای موقعیت شغلی تحلیل سیستم shahabkarimi00 ۳ ۶,۰۲۴ ۰۹ آذر ۱۳۹۹ ۰۳:۳۵ ب.ظ
آخرین ارسال: mohammadasadi1
  مرتبه ایجاد درخت rad.bahar ۱ ۳,۳۶۳ ۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ
آخرین ارسال: rad.bahar
  مرتبه شبه کد rad.bahar ۱ ۲,۳۲۵ ۲۲ مهر ۱۳۹۹ ۰۹:۳۲ ب.ظ
آخرین ارسال: BBumir
  خواص محیط برای عامل سیستم تحلیل تصاویر پزشکی Ali1991khe ۶ ۵,۹۸۷ ۰۴ مهر ۱۳۹۹ ۰۸:۳۲ ق.ظ
آخرین ارسال: Ali1991khe
  حل مساله مرتبه زمانی حلقه های تو در تو sarashahi ۱۶ ۲۲,۸۷۸ ۱۹ خرداد ۱۳۹۹ ۰۱:۱۶ ب.ظ
آخرین ارسال: gillda
  مرتبه زمانی Sanazzz ۱۷ ۲۱,۳۹۸ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۶ ب.ظ
آخرین ارسال: mohsentafresh
  در مصاحبه کارشناس تحلیل گر سیستم چه می پرسند؟ سیما ۱۹۵۶ ۲۸ ۴۵,۹۵۰ ۱۳ اسفند ۱۳۹۸ ۱۱:۴۹ ق.ظ
آخرین ارسال: alma1988

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close