صفحه‌ها: ۱ ۲
سلام دوستان، ممکنه یکی از دوستان بهم پیچیدگی زمانی این الگوریتم رو توضیح بده؟
for i = 1 to n do
j = 2
while j < i do
j = j * j
j = 2
while j < i do
j = j * j
آیا j = j * j داخل حلقه ی while می باشد؟
(۲۶ تیر ۱۳۹۴ ۰۶:۴۸ ب.ظ)faza نوشته شده توسط: حلقه داخلی به ازای هر بار اجرای حلقه بیرونی، تقریبا log i بار اجرا میشه، پس:
(با فرض اینکه داخلی ترین دستور، به عنوان عمل اصلی انتخاب شود)
log 1 + log 2 + log 3 + .... + log n
برابر است با
log (1*2*3*...*n)
برابر است با
[tex]\log\: (n!)[/tex]
که در نهایت، هم رشد با تابع nlogn هست.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
سلام
ممنون بابت پاسختون. من هم مانند شما جواب رو log(n!) به دست آوردم با این تفاوت که نمی دونستم برابر با nlogn می شه و الان که شما فرمودین متوجه شدم. اما این سوال رو من تو تمرینات دانشگاه برکلی دیده بودم که یه جواب مختصر برای هر کدومشون داشت. جوابش برای این سوال :
![[تصویر: 373743_4hky_sss.jpg]](https://img.manesht.ir/373743_4hky_sss.jpg)
می بینید که در پاسخ یه log اضافه تر از پاسخ من و شما داره و همین منو به فکر فرو برده...
(۲۶ تیر ۱۳۹۴ ۰۷:۰۸ ب.ظ)Hasan21 نوشته شده توسط: آیا j = j * j داخل حلقه ی while می باشد؟
بله
(۲۶ تیر ۱۳۹۴ ۰۸:۰۲ ب.ظ)NarimanN2 نوشته شده توسط: این سوال رو من تو تمرینات دانشگاه برکلی دیده بودم که یه جواب مختصر برای هر کدومشون داشت. جوابش برای این سوال :خب قطعا باید دید که چرا معتقده هر بار اجرای حلقه داخلی، loglog i بار تکرار میشه نه log i بار.
می بینید که در پاسخ یه log اضافه تر از پاسخ من و شما داره و همین منو به فکر فرو برده...
من حدس میزنم که اون تمرین یه فرق کوچیک با این تمرین داشته. مثلا شرط پایان حلقه داخلی احتمالا log i بوده نه خود i یا امثالهم!
حلقه ی اول (همون for) مسلما n بار تکرار میشه پس داریم
n* . . .
حالا میریم به قسمت
j = 2
while j < i do
j = j * j
اشتباهی که شما داشتید اینه که این تکه از برنامه رو بدین صورت در نظر گرفتید
j = 2
while j < i do
j = j * 2
اگه برنامه بدین صورت بود آره، جواب nlogn میشد
ولی در اینجا برنامه j رو هر بار در خودش رب میکنه
یعنی مقادیر j به صورت زیر رشد میکنه
۲ و ۴ و ۱۶ و ۲۵۶ و ۲۵۶*۲۵۶ و ...
که این رشد برابر با loglogn هست، این قسمت سوال یکی از دانشگاه ها ایران هم بوده
پس جواب نهایی میشه nloglogn، هر جاش توضیح بیشتر خواستید بگید توضیح میدم
(۲۶ تیر ۱۳۹۴ ۱۰:۴۴ ب.ظ)sixsixsix نوشته شده توسط: اشتباهی که شما داشتید اینه که این تکه از برنامه رو بدین صورت در نظر گرفتیدبله کاملا حق با شماست.
j = 2
while j < i do
j = j * 2
اگه برنامه بدین صورت بود آره، جواب nlogn میشد
. . .
پس جواب نهایی میشه nloglogn، هر جاش توضیح بیشتر خواستید بگید توضیح میدم
من اشتباه دیدم سوال رو. می بخشید.
قطعا جواب این سوال nlogn نیست. اما اینکه چجوری loglogn از توش در میاد رو نمیدونم.
(۲۶ تیر ۱۳۹۴ ۱۰:۴۴ ب.ظ)sixsixsix نوشته شده توسط: حلقه ی اول (همون for) مسلما n بار تکرار میشه پس داریم
n* . . .
حالا میریم به قسمت
j = 2
while j < i do
j = j * j
اشتباهی که شما داشتید اینه که این تکه از برنامه رو بدین صورت در نظر گرفتید
j = 2
while j < i do
j = j * 2
اگه برنامه بدین صورت بود آره، جواب nlogn میشد
ولی در اینجا برنامه j رو هر بار در خودش رب میکنه
یعنی مقادیر j به صورت زیر رشد میکنه
۲ و ۴ و ۱۶ و ۲۵۶ و ۲۵۶*۲۵۶ و ...
که این رشد برابر با loglogn هست، این قسمت سوال یکی از دانشگاه ها ایران هم بوده
پس جواب نهایی میشه nloglogn، هر جاش توضیح بیشتر خواستید بگید توضیح میدم
ممنون متوجه شدم!
(۲۶ تیر ۱۳۹۴ ۱۰:۴۴ ب.ظ)sixsixsix نوشته شده توسط: حلقه ی اول (همون for) مسلما n بار تکرار میشه پس داریم
n* . . .
حالا میریم به قسمت
j = 2
while j < i do
j = j * j
اشتباهی که شما داشتید اینه که این تکه از برنامه رو بدین صورت در نظر گرفتید
j = 2
while j < i do
j = j * 2
اگه برنامه بدین صورت بود آره، جواب nlogn میشد
ولی در اینجا برنامه j رو هر بار در خودش رب میکنه
یعنی مقادیر j به صورت زیر رشد میکنه
۲ و ۴ و ۱۶ و ۲۵۶ و ۲۵۶*۲۵۶ و ...
که این رشد برابر با loglogn هست، این قسمت سوال یکی از دانشگاه ها ایران هم بوده
پس جواب نهایی میشه nloglogn، هر جاش توضیح بیشتر خواستید بگید توضیح میدم
پس چرا از مقدار ۱۶ به ۲ میرویم یعنی ۲=loglog16 میشه ولی در دنباله بعد از ۱۶ مقدار ۴ رو داریم. [ با توجه به این دنباله ۲ و ۴ و ۱۶ و ۲۵۶ و ۲۵۶*۲۵۶ و ...]
(۲۷ تیر ۱۳۹۴ ۰۵:۴۵ ق.ظ)flower1 نوشته شده توسط:(26 تیر ۱۳۹۴ ۱۰:۴۴ ب.ظ)sixsixsix نوشته شده توسط: حلقه ی اول (همون for) مسلما n بار تکرار میشه پس داریم
n* . . .
حالا میریم به قسمت
j = 2
while j < i do
j = j * j
اشتباهی که شما داشتید اینه که این تکه از برنامه رو بدین صورت در نظر گرفتید
فقط اینکه خیلی راحت میشه فهمید قسمت j=j*j به ازای i=2 صفر تکرار و به ازای i=4 یکبار تکرار، به ازای n=16 دوبار تکرار و ... داریم
پس پیچیدگی زمانی قسمت داخلی برنامه loglogn میشود
یعنی
loglog 2 = 0
loglog 4 = 1
loglog 16 =2
. . .
j = 2
while j < i do
j = j * 2
اگه برنامه بدین صورت بود آره، جواب nlogn میشد
ولی در اینجا برنامه j رو هر بار در خودش رب میکنه
یعنی مقادیر j به صورت زیر رشد میکنه
۲ و ۴ و ۱۶ و ۲۵۶ و ۲۵۶*۲۵۶ و ...
که این رشد برابر با loglogn هست، این قسمت سوال یکی از دانشگاه ها ایران هم بوده
پس جواب نهایی میشه nloglogn، هر جاش توضیح بیشتر خواستید بگید توضیح میدم
پس چرا از مقدار ۱۶ به ۲ میرویم یعنی ۲=loglog16 میشه ولی در دنباله بعد از ۱۶ مقدار ۴ رو داریم. [ با توجه به این دنباله ۲ و ۴ و ۱۶ و ۲۵۶ و ۲۵۶*۲۵۶ و ...]
ببخشید منظورتون رو متوجه نشدم! اگه امکان داره بیشتر توضیح بدید!
فقط اینو بگم که خیلی راحت میشه فهمید که برنامه به ازای i=2 صفر تکرار، به ازای i=4 یکبار تکرار و به ازای i=16 دوبار تکرار و ... دارد
loglog2 = 0
loglog 4 = 1
loglog 16 =2
.....
جواب اقای six six sixدرست جواب n loglognهست من سرعتم کمه نتونستم عکسهای پیوست رو ببینم اما..
واسه این گونه سوالات
بهتره اینجوری عمل کنید
چون مرتبه میخواد عدد گذاری اصولا کار خطرناکیه شاید بعضی ها جواب درست هم داخلش در بیاد اما همیشه درست نمیشه
باید ابتدا j هایی که که دستور مورد نظر در حلقه دوم رو اجرا میکنه رو بنویسید یعنی به ازا چه jهایی دستور مورد نظر اجرا میشه
تیپ اون ر وبرحسب به متغییر کمکی دیگه مثلا k بنویسید بعد متغییر کمییتون مثلا k رو محاسبه کنید
(باید طوری تیپ k را بسازیم ویا با hیجاد کنیم که یه دنیاله عددی از اعدادی که اون خط مورد نظر رو ( j=j*j) اجراکردند رو بدست بیاریم بطوری که یک دنباله از اعداد با فاصله اندیس ۱ ایجاد بشه.
پس مقادیر kمیشه ۲ ۴ ۱۶ ۲۵۶ ........
حال این دنباله رو طوری باید ساخته با فاصله اندیسهای یک برای راحتی کار ومحاسبه مقدار متغییر کمکی یعنی k تا مرتبه بدست بیاد
بعدش با متغییر اصلی برابر هم قرار میدین و با لگاریتم گیری از ۲طرف جواب بدست میاد
من نمیتونم خوب بنویسم چون امکانات نگارشی ندارم اما شما
مرحله دوم
بجای ۲ بذارید ۲به توان ۱
به جای ۴ بذارید ۲ به توان ۲
به جای ۱۶ بذارید ۲به توان ۴
به جای ۲۵۶ بذارید ۲ به توان ۸
......
مرحله سوم
این که بجای ۲توان دنباله رو ۳ توانی بکنید
یعنی
بجای ۲ به توان ۱ مرحله دوم
ببنویسید ۲ به توان ۲ به توان ۰
بجای ۲به توان ۲ مرحله دوم
در مرجله سوم بنویسید ۲ به توان۲ به توان ۱= ۲به توان ۲ مرحله دوم
بجای ۲به توان۸ مرحله دوم بنویسید ۲ به توان ۲ به توان ۳
و نهایتا اخرین مقدار ۲ به توان ۲ به توان k
k اخرین مقداری هست که متغییر ما در حلقه اجرا میشه
بعدش این دنباله
رو برابر با مقدار نهایی متغییر اصلی حلقه یعنی j قرار بدید مقدار نهایی j دقیقا برا i هست ومقدار نهایی i هم برابر n خواهد بود
پس الان در قدم اخر شما مقدار N=2^2^k قرار میدید (n= دو به توان ۲ به توان k)
با بار اول لگاریتم گرفتن از ۲طرف میشه
logn= *2^k
و بار دوم لگاریتم گرفتن جواب میشه
loglog N=k
پس جواب حلقه داخلی شد log log n
حلقه بیرونی هم که N
بود
جواب نهایی میشه
nloglogn
امیداورم متوجه شده باشید
خیر جز حلقه داخلی نیست چون حلقه داخلی بریس باز و بسته نداره و وقتی نداره فقط یه دستور بعد حلقه شاملش میشه
NarimanN2 نوشته شده توسط: ... این سوال رو من تو تمرینات دانشگاه برکلی دیده بودم ...:سلام دوست عزیز.آیا امکانش هست این تمرینات ساختمان داده دانشگاه برکلی رو در اختیار ما هم بذارید؟
تو اینترنت گشتم،چیزی پیدا نکردم
(۰۴ مرداد ۱۳۹۴ ۰۳:۰۱ ق.ظ)azbycxx نوشته شده توسط:بفرماییدNarimanN2 نوشته شده توسط: ... این سوال رو من تو تمرینات دانشگاه برکلی دیده بودم ...:سلام دوست عزیز.آیا امکانش هست این تمرینات ساختمان داده دانشگاه برکلی رو در اختیار ما هم بذارید؟
تو اینترنت گشتم،چیزی پیدا نکردم
(۰۵ مرداد ۱۳۹۴ ۰۴:۰۹ ب.ظ)NarimanN2 نوشته شده توسط:واقعا ممنون.دستتون درد نکنه(04 مرداد ۱۳۹۴ ۰۳:۰۱ ق.ظ)azbycxx نوشته شده توسط:بفرماییدNarimanN2 نوشته شده توسط: ... این سوال رو من تو تمرینات دانشگاه برکلی دیده بودم ...:سلام دوست عزیز.آیا امکانش هست این تمرینات ساختمان داده دانشگاه برکلی رو در اختیار ما هم بذارید؟
تو اینترنت گشتم،چیزی پیدا نکردم
سلام
ممنون از بابت این فایل
اما فقط یک صفحه هست این تمرینات ؟!!
مابقیش و نداری بی زحمت برامون بزاری اینجا ؟
یا لینکش رو اینجا امکان داره بزاری واسه همه ؟