سلام دوستان من توی جواب این سوال مشکل دارم ؟ هم پوران پژوهش هم مقسمی هردو مثل هم حلش کردن اگه میشه لطف کنید به من بگید اشکالم کجاست؟
سوال گفته که یک آرایه داریم که میدونیم مجموع درایه هاش برابر 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) حالا نمیدونم چرا جوابم اشتباه ِ
به ازای r=1 حلقه اول ،حلقه دوم از ۱ تا v[1 اجرا میشه یعنی v[1 بار به همین ترتیب به ازای r=2 هم v[2 بار اجرا میشه و الی آخر یعنی برای r=n هم v[n بار اجرا میشه پس جمعا v[1 +v[2+...........v[n بار حلقه‌ها اجرا میشن که میشه همون Q بار
توجه کنید که دو حلقه از هم مستقل نیستند که مرتبه آنها رو در هم ضرب کنیم باید مرتبه رو به ازای مقادیر مختلف حلقه اول برای حلقه دوم حساب کنیم و جمع بزنیم مثل حالتی که برای حلقه دوم داشتیم j<=i .
شما حالتی رو در نظر بگیر که Q=100 باشه و n=5 حالا [۰]v تا [۴]v مساوی ۱ باشه و [۵]v برابر ۹۶ باشه حالا جواب Q+n میشه ببینید فرمایش افاق درست هستش دو حلقه مستقل نیستند برای اینجور سوالها فرض بزرگترین مقدار رو در نظر بگیر به دفعات قبل هم هیچ کاری نداشته باش
مورد مهمتر توی این سوالها اینه که تشخیص بدید که چرا جواب اوی Q یا اوی n نمیشود.
(۲۰ دى ۱۳۸۹ ۱۲:۳۳ ب.ظ)حامد نوشته شده توسط: مورد مهمتر توی این سوالها اینه که تشخیص بدید که چرا جواب اوی Q یا اوی n نمیشود.
چه جوری؟؟؟؟
به نظر من:
اگر زمان داخلی ترین جمله رو میخاست همون اوی Q میشد.
اما حالا که مرتبه کل تابع رو میخاد در حالتی که Q کمتر از n هست for اولی و دومی n بار تکرار میش که باید حاصل بشه اوی n.
(۲۰ دى ۱۳۸۹ ۰۱:۵۳ ب.ظ)afagh1389 نوشته شده توسط:افاق مهمه دیگه به هر حال یک Q موجود هست باید یک نقشی داشته باشه هان!!!!(20 دى ۱۳۸۹ ۱۲:۳۳ ب.ظ)حامد نوشته شده توسط: مورد مهمتر توی این سوالها اینه که تشخیص بدید که چرا جواب اوی Q یا اوی n نمیشود.
چه جوری؟؟؟؟
صاحب تاپیک صورت سوال را کامل ننوشته اند.در صورت سوال(دولتی ۷۶ یا آزاد ۸۱ و ۸۶) دقیقا ذکر شده است که آرایه‌ی مورد نظر از اعداد صحیح می باشد.در نتیجه ما نمی توانیم هیچ نتیجه گیری مبنی بر کوچکتر یا بزرگتر بودن q از n بگیریم.ممکنه مثلا جمع این n تا عدد مثلا بشه ۱/پس نمی تونیم بگیم اوی q.از طرفی هم ممکنه جمع این n تا عدد بشه مثلا n بتوان دو.پس نمی تونیم هم بگیم اوی n.پس با توجه به اینکه نمی تونیم n وq را مقایسه کنیم جواب اوی n+q میشود.
جالبی قضیه جایی است که مولفان محترم کتاب های کنکوری هر کدام به نحوی این سوال رو پیچوندند و رفتند! یکی گفته توی گزینه‌ها اوی q نیست پس جواب میشه اوی n+q! یکی دیگه گفته تعداد تکرار حلقه‌ی for بیرونی را هم می خواسته بشماره و ...!!!
حالا اگر در صورت سوال آرایه مورد نظر از اعداد طبیعی تعریف شده بود ما بدون شک می تونستیم بگیم که Q بزرگتر مساوی n است و در نتیجه جواب اوی q میشود.
سلام دوستان
میشه این چندتابع رو براساس مرتبه رشدشون رتبه بندی کنید (بادلیلش)
n^3 , (lgn)! , n^lglgn
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