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

تست الگوریتم _ آزاد ۸۱و۸۶ (مرتبه اجرای تابع )

ارسال:
  

farshad_pickup پرسیده:

تست الگوریتم _ آزاد ۸۱و۸۶ (مرتبه اجرای تابع )

سلام دوستان من توی جواب این سوال مشکل دارم ؟ هم پوران پژوهش هم مقسمی هردو مثل هم حلش کردن اگه میشه لطف کنید به من بگید اشکالم کجاست؟
سوال گفته که یک آرایه داریم که میدونیم مجموع درایه هاش برابر Q است
کد:
v[1]+v[2]+...+v[n] = Q
مرتبه‌ی اجرای تابع زیر چیست
کد:
for r:= 1 to n do
for s:= 1 to v[r] do
tmp:=tmp+10
هر دو گفتن جواب
O(Q+n) ولی من میگم چون حد اکثر اجرای حلقه داخلی Q است پس از مرتبه O(Q*n) حالا نمیدونم چرا جوابم اشتباه ِ
مشاهده‌ی وب‌سایت کاربر

۰
ارسال:
  

حامد پاسخ داده:

RE: مرتبه اجرای تابع -(آزاد ۸۱و۸۶)

صاحب تاپیک صورت سوال را کامل ننوشته اند.در صورت سوال(دولتی ۷۶ یا آزاد ۸۱ و ۸۶) دقیقا ذکر شده است که آرایه‌ی مورد نظر از اعداد صحیح می باشد.در نتیجه ما نمی توانیم هیچ نتیجه گیری مبنی بر کوچکتر یا بزرگتر بودن q از n بگیریم.ممکنه مثلا جمع این n تا عدد مثلا بشه ۱/پس نمی تونیم بگیم اوی q.از طرفی هم ممکنه جمع این n تا عدد بشه مثلا n بتوان دو.پس نمی تونیم هم بگیم اوی n.پس با توجه به اینکه نمی تونیم n وq را مقایسه کنیم جواب اوی n+q میشود.
جالبی قضیه جایی است که مولفان محترم کتاب های کنکوری هر کدام به نحوی این سوال رو پیچوندند و رفتند! یکی گفته توی گزینه‌ها اوی q نیست پس جواب میشه اوی n+q‌! یکی دیگه گفته تعداد تکرار حلقه‌ی for بیرونی را هم می خواسته بشماره و ...!!!
حالا اگر در صورت سوال آرایه مورد نظر از اعداد طبیعی تعریف شده بود ما بدون شک می تونستیم بگیم که Q بزرگتر مساوی n است و در نتیجه جواب اوی q میشود.

۰
ارسال:
  

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

مرتبه اجرای تابع -(آزاد ۸۱و۸۶)

به ازای r=1 حلقه اول ،حلقه دوم از ۱ تا v[1 اجرا میشه یعنی v[1 بار به همین ترتیب به ازای r=2 هم v[2 بار اجرا میشه و الی آخر یعنی برای r=n هم v[n بار اجرا میشه پس جمعا v[1 +v[2+...........v[n بار حلقه‌ها اجرا میشن که میشه همون Q بار

توجه کنید که دو حلقه از هم مستقل نیستند که مرتبه آنها رو در هم ضرب کنیم باید مرتبه رو به ازای مقادیر مختلف حلقه اول برای حلقه دوم حساب کنیم و جمع بزنیم مثل حالتی که برای حلقه دوم داشتیم j<=i .

۰
ارسال:
  

javadjj پاسخ داده:

مرتبه اجرای تابع -(آزاد ۸۱و۸۶)

شما حالتی رو در نظر بگیر که Q=100 باشه و n=5 حالا [۰]v تا [۴]v مساوی ۱ باشه و [۵]v برابر ۹۶ باشه حالا جواب Q+n میشه ببینید فرمایش افاق درست هستش دو حلقه مستقل نیستند برای اینجور سوال‌ها فرض بزرگترین مقدار رو در نظر بگیر به دفعات قبل هم هیچ کاری نداشته باش

۰
ارسال:
  

حامد پاسخ داده:

RE: مرتبه اجرای تابع -(آزاد ۸۱و۸۶)

مورد مهمتر توی این سوالها اینه که تشخیص بدید که چرا جواب اوی Q یا اوی n نمیشود.

ارسال:
  

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

RE: مرتبه اجرای تابع -(آزاد ۸۱و۸۶)

(۲۰ دى ۱۳۸۹ ۱۲:۳۳ ب.ظ)حامد نوشته شده توسط:  مورد مهمتر توی این سوالها اینه که تشخیص بدید که چرا جواب اوی Q یا اوی n نمیشود.

چه جوری؟؟؟؟
یافتن تمامی ارسال‌های این کاربر

۰
ارسال:
  

sepid پاسخ داده:

مرتبه اجرای تابع -(آزاد ۸۱و۸۶)

به نظر من:
اگر زمان داخلی ترین جمله رو میخاست همون اوی Q میشد.
اما حالا که مرتبه کل تابع رو میخاد در حالتی که Q کمتر از n هست for اولی و دومی n بار تکرار میش که باید حاصل بشه اوی n.
مشاهده‌ی وب‌سایت کاربر

۰
ارسال:
  

ارگشت پاسخ داده:

مرتبه رشد توابع

سلام دوستان

میشه این چندتابع رو براساس مرتبه رشدشون رتبه بندی کنید (بادلیلش)

n^3 , (lgn)! , n^lglgn

۰
ارسال:
  

ROZA پاسخ داده:

RE: مرتبه اجرای تابع -(آزاد ۸۱و۸۶)

n^3 که تکلیفش مشخصه

n^log logn برابر هست با lg n^lg n طبق خواص لگاریتم .پس یه جورایی میشه یه تابع نمایی که رشدش از n^3 بیشتره

!(lgn)هم با استفاده از فرمول استر لینگ قابل حله .درپیوست دقت کنید.
ساده شده‌ی فرمول استرلینگ میگه رشد n ^n از ‌! n بیشتره

حالا اگر به جایlog n ‌، n بگذارید،متوجه میشید که سرعت رشد !(lgn) از log n^log n کمتره .
پس به این صورت میشه:
n^3 < (logn)! < n^log logn


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



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
Exclamation سلام لطفاً یکی به من بگه مرتبه زمانی ها چطوری به log تبدیل میشن فرمول داره؟؟ Azadam ۶ ۴,۸۲۴ ۰۶ دى ۱۴۰۰ ۰۹:۰۲ ق.ظ
آخرین ارسال: Soldier's life
  مرتبه ایجاد درخت rad.bahar ۱ ۳,۳۵۸ ۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ
آخرین ارسال: rad.bahar
  مرتبه شبه کد rad.bahar ۱ ۲,۳۲۱ ۲۲ مهر ۱۳۹۹ ۰۹:۳۲ ب.ظ
آخرین ارسال: BBumir
  چگونه این خطا را موقع اجرای sql server 2014 رفع کنم ؟ farahnaz ۲ ۳,۰۲۱ ۱۹ مهر ۱۳۹۹ ۰۲:۱۸ ق.ظ
آخرین ارسال: farahnaz
  حل مساله مرتبه زمانی حلقه های تو در تو sarashahi ۱۶ ۲۲,۸۴۹ ۱۹ خرداد ۱۳۹۹ ۰۱:۱۶ ب.ظ
آخرین ارسال: gillda
  اجرای نرم افزار ویندوز در اندروید elecomco ۰ ۳,۰۵۳ ۰۴ خرداد ۱۳۹۹ ۰۸:۳۷ ب.ظ
آخرین ارسال: elecomco
  تابع مولد ss311 ۰ ۱,۴۸۲ ۲۶ اردیبهشت ۱۳۹۹ ۱۲:۴۹ ب.ظ
آخرین ارسال: ss311
  مرتبه زمانی Sanazzz ۱۷ ۲۱,۳۸۸ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۶ ب.ظ
آخرین ارسال: mohsentafresh
  یادگیری برنامه نویسی تا اجرای پروژه های بزرگ The BesT ۳ ۳,۶۱۴ ۱۲ آذر ۱۳۹۸ ۰۳:۵۸ ب.ظ
آخرین ارسال: marvelous
  مرتبه زمانی یافتن قطر Sepideh96 ۲ ۳,۷۷۷ ۰۸ آذر ۱۳۹۸ ۰۴:۳۴ ب.ظ
آخرین ارسال: erfan30

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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