۰
subtitle
ارسال: #۱
تست الگوریتم _ آزاد ۸۱و۸۶ (مرتبه اجرای تابع )
سلام دوستان من توی جواب این سوال مشکل دارم ؟ هم پوران پژوهش هم مقسمی هردو مثل هم حلش کردن اگه میشه لطف کنید به من بگید اشکالم کجاست؟
سوال گفته که یک آرایه داریم که میدونیم مجموع درایه هاش برابر Q است
مرتبه‌ی اجرای تابع زیر چیست
هر دو گفتن جواب
O(Q+n) ولی من میگم چون حد اکثر اجرای حلقه داخلی Q است پس از مرتبه O(Q*n) حالا نمیدونم چرا جوابم اشتباه ِ
سوال گفته که یک آرایه داریم که میدونیم مجموع درایه هاش برابر Q است
کد:
v[1]+v[2]+...+v[n] = Qکد:
for r:= 1 to n do
for s:= 1 to v[r] do
tmp:=tmp+10O(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 میشود.
جالبی قضیه جایی است که مولفان محترم کتاب های کنکوری هر کدام به نحوی این سوال رو پیچوندند و رفتند! یکی گفته توی گزینه‌ها اوی 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 .
توجه کنید که دو حلقه از هم مستقل نیستند که مرتبه آنها رو در هم ضرب کنیم باید مرتبه رو به ازای مقادیر مختلف حلقه اول برای حلقه دوم حساب کنیم و جمع بزنیم مثل حالتی که برای حلقه دوم داشتیم j<=i .
۰
ارسال: #۴
مرتبه اجرای تابع -(آزاد ۸۱و۸۶)
شما حالتی رو در نظر بگیر که Q=100 باشه و n=5 حالا [۰]v تا [۴]v مساوی ۱ باشه و [۵]v برابر ۹۶ باشه حالا جواب Q+n میشه ببینید فرمایش افاق درست هستش دو حلقه مستقل نیستند برای اینجور سوالها فرض بزرگترین مقدار رو در نظر بگیر به دفعات قبل هم هیچ کاری نداشته باش
۰
ارسال: #۵
RE: مرتبه اجرای تابع -(آزاد ۸۱و۸۶)
مورد مهمتر توی این سوالها اینه که تشخیص بدید که چرا جواب اوی Q یا اوی n نمیشود.
ارسال: #۶
RE: مرتبه اجرای تابع -(آزاد ۸۱و۸۶)
۰
ارسال: #۷
مرتبه اجرای تابع -(آزاد ۸۱و۸۶)
به نظر من:
اگر زمان داخلی ترین جمله رو میخاست همون اوی Q میشد.
اما حالا که مرتبه کل تابع رو میخاد در حالتی که Q کمتر از n هست for اولی و دومی n بار تکرار میش که باید حاصل بشه اوی n.
اگر زمان داخلی ترین جمله رو میخاست همون اوی Q میشد.
اما حالا که مرتبه کل تابع رو میخاد در حالتی که Q کمتر از n هست for اولی و دومی n بار تکرار میش که باید حاصل بشه اوی n.
۰
ارسال: #۸
مرتبه رشد توابع
سلام دوستان
میشه این چندتابع رو براساس مرتبه رشدشون رتبه بندی کنید (بادلیلش)
n^3 , (lgn)! , n^lglgn
میشه این چندتابع رو براساس مرتبه رشدشون رتبه بندی کنید (بادلیلش)
n^3 , (lgn)! , n^lglgn
۰
ارسال: #۹
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
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
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close