تالار گفتمان مانشت
ارشد۹۰ آزاد-پیچیدگی - نسخه‌ی قابل چاپ

ارشد۹۰ آزاد-پیچیدگی - 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 هستش.حالا چون تو این سوال تعداد سطرها و ستون‌ها برابر هست پس داریم:
[tex]O(n n)=O(2n)=O(n)[/tex]

(۰۳ شهریور ۱۳۹۰ ۱۱:۲۹ ب.ظ)**sara** نوشته شده توسط:  سوال اول گزینه ۲ درسته
بعیده گزینه دو درست باشه چون فکر می کنم اون قسمت که گفته b یک عدد صحیح n بیتی هست کار رو خراب می کنه.

این جدول young توی کدوم منبع هست؟ می خوام مطالعه کنم

پس می شه لطفاً راه حل درست سوال اول رو بگین؟

ممنون

ارشد۹۰ آزاد-پیچیدگی - blackhalo1989 - 04 شهریور ۱۳۹۰ ۰۲:۳۳ ق.ظ

تو CLRS.بر اساس ویرایش سوم زبان اصلی:
Chapter 6 Heapsort->Problems->6-3 Young tableaus