۰
subtitle
ارسال: #۱
ارشد۹۰ آزاد-پیچیدگی
فرض کنید 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)
o(log n)
o(b)
o(a)
o(n)
--------------------------------------------
ماتریس A n*nرا در نظربگیرید.که در آن همه‌ی سطرهای ماتریس ازچب به راست و همه‌ی ستون های ماتریس ازبالا به پایین همگی صعودی هستند.برای یافتن عنصر xبهترین الگوریتم ازکدام مرتبه است؟
o(nlog n)
o(log n)
o(n^2)
o(n)
۰
۰
۰
ارسال: #۴
RE: ارشد۹۰ آزاد-پیچیدگی
به یه همچین ماتریس یا جدولی میگن جدول young.اگر چنین جدولی دارای m سطر و n ستون باشه اونوقت پیچیدگی یافتن یک عنصر برابر با بیگ اوی m+n هستش.حالا چون تو این سوال تعداد سطرها و ستون‌ها برابر هست پس داریم:
[tex]O(n n)=O(2n)=O(n)[/tex]
[tex]O(n n)=O(2n)=O(n)[/tex]
(۰۳ شهریور ۱۳۹۰ ۱۱:۲۹ ب.ظ)**sara** نوشته شده توسط: سوال اول گزینه ۲ درستهبعیده گزینه دو درست باشه چون فکر می کنم اون قسمت که گفته b یک عدد صحیح n بیتی هست کار رو خراب می کنه.
ارسال: #۵
RE: ارشد۹۰ آزاد-پیچیدگی
(۰۴ شهریور ۱۳۹۰ ۰۱:۰۷ ق.ظ)mfXpert نوشته شده توسط: به یه همچین ماتریس یا جدولی میگن جدول young.اگر چنین جدولی دارای m سطر و n ستون باشه اونوقت پیچیدگی یافتن یک عنصر برابر با بیگ اوی m+n هستش.حالا چون تو این سوال تعداد سطرها و ستون‌ها برابر هست پس داریم:
[tex]O(n n)=O(2n)=O(n)[/tex]
(۰۳ شهریور ۱۳۹۰ ۱۱:۲۹ ب.ظ)**sara** نوشته شده توسط: سوال اول گزینه ۲ درستهبعیده گزینه دو درست باشه چون فکر می کنم اون قسمت که گفته b یک عدد صحیح n بیتی هست کار رو خراب می کنه.
این جدول young توی کدوم منبع هست؟ می خوام مطالعه کنم
پس می شه لطفاً راه حل درست سوال اول رو بگین؟
ممنون
۰
ارسال: #۶
ارشد۹۰ آزاد-پیچیدگی
تو CLRS.بر اساس ویرایش سوم زبان اصلی:
Chapter 6 Heapsort->Problems->6-3 Young tableaus
Chapter 6 Heapsort->Problems->6-3 Young tableaus
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close