ارشد۹۰ آزاد-پیچیدگی - نسخهی قابل چاپ |
ارشد۹۰ آزاد-پیچیدگی - sahar_2000 - 03 شهریور ۱۳۹۰ ۰۴:۱۵ ب.ظ
فرض کنید aیک عددحقیقی وbیک عددصحیح مثبت nبیتیاست.بهترین الگوریتم برای محاسبهی a^bدارای کدام پیچیدگی است؟(فرض کنیدهرعمل ضرب دریک واحدزمانی اجرامیشود) o(log n) o(b) o(a) o(n) -------------------------------------------- ماتریس A n*nرا در نظربگیرید.که در آن همهی سطرهای ماتریس ازچب به راست و همهی ستون های ماتریس ازبالا به پایین همگی صعودی هستند.برای یافتن عنصر xبهترین الگوریتم ازکدام مرتبه است؟ o(nlog n) o(log n) o(n^2) o(n) |
ارشد۹۰ آزاد-پیچیدگی - Morteza_s - 03 شهریور ۱۳۹۰ ۱۱:۲۲ ب.ظ
به نظر من گزینه یک بشه سوال دوم |
RE: ارشد۹۰ آزاد-پیچیدگی - **sara** - 03 شهریور ۱۳۹۰ ۱۱:۲۹ ب.ظ
به نظر من هم سوال دوم گزینه ۴ درسته سوال اول گزینه ۲ درسته |
RE: ارشد۹۰ آزاد-پیچیدگی - mfXpert - 04 شهریور ۱۳۹۰ ۰۱:۰۷ ق.ظ
به یه همچین ماتریس یا جدولی میگن جدول young.اگر چنین جدولی دارای m سطر و n ستون باشه اونوقت پیچیدگی یافتن یک عنصر برابر با بیگ اوی m+n هستش.حالا چون تو این سوال تعداد سطرها و ستونها برابر هست پس داریم: [tex]O(n n)=O(2n)=O(n)[/tex] (۰۳ شهریور ۱۳۹۰ ۱۱:۲۹ ب.ظ)**sara** نوشته شده توسط: سوال اول گزینه ۲ درستهبعیده گزینه دو درست باشه چون فکر می کنم اون قسمت که گفته b یک عدد صحیح n بیتی هست کار رو خراب می کنه. |
RE: ارشد۹۰ آزاد-پیچیدگی - **sara** - 04 شهریور ۱۳۹۰ ۰۲:۱۷ ق.ظ
(۰۴ شهریور ۱۳۹۰ ۰۱:۰۷ ق.ظ)mfXpert نوشته شده توسط: به یه همچین ماتریس یا جدولی میگن جدول young.اگر چنین جدولی دارای m سطر و n ستون باشه اونوقت پیچیدگی یافتن یک عنصر برابر با بیگ اوی m+n هستش.حالا چون تو این سوال تعداد سطرها و ستونها برابر هست پس داریم: این جدول young توی کدوم منبع هست؟ می خوام مطالعه کنم پس می شه لطفاً راه حل درست سوال اول رو بگین؟ ممنون |
ارشد۹۰ آزاد-پیچیدگی - blackhalo1989 - 04 شهریور ۱۳۹۰ ۰۲:۳۳ ق.ظ
تو CLRS.بر اساس ویرایش سوم زبان اصلی: Chapter 6 Heapsort->Problems->6-3 Young tableaus |