(۲۶ تیر ۱۳۹۴ ۱۰:۴۴ ب.ظ)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 نوشته شده توسط:  ... این سوال رو من تو تمرینات دانشگاه برکلی دیده بودم ...:

سلام دوست عزیز.آیا امکانش هست این تمرینات ساختمان داده دانشگاه برکلی رو در اختیار ما هم بذارید؟
تو اینترنت گشتم،چیزی پیدا نکردم

بفرمایید

واقعا ممنون.دستتون درد نکنه

سلام
ممنون از بابت این فایل
اما فقط یک صفحه هست این تمرینات ؟!!
مابقیش و نداری بی زحمت برامون بزاری اینجا ؟
یا لینکش رو اینجا امکان داره بزاری واسه همه ؟

آیا j = j * j داخل حلقه ی while می باشد؟

خیر جز حلقه داخلی نیست چون حلقه داخلی بریس باز و بسته نداره و وقتی نداره فقط یه دستور بعد حلقه شاملش میشه

باعرض سلام وخسته نباشید من توقسمت مبحث پیچیدگی ومرتبه زمانی خیلی اشکال دارم وعضومدرسان شریف هستم ازهفته آینده آزمون هایم شروع میشه خیلی استرس گرفتم تموم تست های روش تغییرمتغییروقضیه اصلی روهیچ بلدنیستم روش تغیبرمتغیرصفحه ۲۷مدرسان شریف تس های صفحه ۳۳به بعدلطفاراهنماییم کنیدباتشکر