۲
subtitle
ارسال: #۱
  
پیچیدگی زمانی این الگوریتم چیست؟
سلام دوستان، ممکنه یکی از دوستان بهم پیچیدگی زمانی این الگوریتم رو توضیح بده؟
for i = 1 to n do
j = 2
while j < i do
j = j * j
j = 2
while j < i do
j = j * j
۴
ارسال: #۲
  
پیچیدگی زمانی این الگوریتم چیست؟
حلقه ی اول (همون 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، هر جاش توضیح بیشتر خواستید بگید توضیح میدم
n* . . .
حالا میریم به قسمت
j = 2
while j < i do
j = j * j
اشتباهی که شما داشتید اینه که این تکه از برنامه رو بدین صورت در نظر گرفتید
j = 2
while j < i do
j = j * 2
اگه برنامه بدین صورت بود آره، جواب nlogn میشد
ولی در اینجا برنامه j رو هر بار در خودش رب میکنه
یعنی مقادیر j به صورت زیر رشد میکنه
۲ و ۴ و ۱۶ و ۲۵۶ و ۲۵۶*۲۵۶ و ...
که این رشد برابر با loglogn هست، این قسمت سوال یکی از دانشگاه ها ایران هم بوده
پس جواب نهایی میشه nloglogn، هر جاش توضیح بیشتر خواستید بگید توضیح میدم
ارسال: #۳
  
RE: پیچیدگی زمانی این الگوریتم چیست؟
(۲۶ تیر ۱۳۹۴ ۱۰:۴۴ ب.ظ)sixsixsix نوشته شده توسط: اشتباهی که شما داشتید اینه که این تکه از برنامه رو بدین صورت در نظر گرفتیدبله کاملا حق با شماست.
j = 2
while j < i do
j = j * 2
اگه برنامه بدین صورت بود آره، جواب nlogn میشد
. . .
پس جواب نهایی میشه nloglogn، هر جاش توضیح بیشتر خواستید بگید توضیح میدم
من اشتباه دیدم سوال رو. می بخشید.
قطعا جواب این سوال nlogn نیست. اما اینکه چجوری loglogn از توش در میاد رو نمیدونم.
ارسال: #۴
  
RE: پیچیدگی زمانی این الگوریتم چیست؟
(۲۶ تیر ۱۳۹۴ ۱۰:۴۴ ب.ظ)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، هر جاش توضیح بیشتر خواستید بگید توضیح میدم
ممنون متوجه شدم!
ارسال: #۵
  
RE: پیچیدگی زمانی این الگوریتم چیست؟
(۲۶ تیر ۱۳۹۴ ۱۰:۴۴ ب.ظ)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 میشه ولی در دنباله بعد از ۱۶ مقدار ۴ رو داریم. [ با توجه به این دنباله ۲ و ۴ و ۱۶ و ۲۵۶ و ۲۵۶*۲۵۶ و ...]
ارسال: #۶
  
RE: پیچیدگی زمانی این الگوریتم چیست؟
(۲۷ تیر ۱۳۹۴ ۰۵:۴۵ ق.ظ)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
.....
۱
ارسال: #۷
  
RE: پیچیدگی زمانی این الگوریتم چیست؟
جواب اقای 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
امیداورم متوجه شده باشید
واسه این گونه سوالات
بهتره اینجوری عمل کنید
چون مرتبه میخواد عدد گذاری اصولا کار خطرناکیه شاید بعضی ها جواب درست هم داخلش در بیاد اما همیشه درست نمیشه
باید ابتدا 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
امیداورم متوجه شده باشید
۱
ارسال: #۸
  
RE: پیچیدگی زمانی این الگوریتم چیست؟
ارسال: #۹
  
RE: پیچیدگی زمانی این الگوریتم چیست؟
ارسال: #۱۰
  
RE: پیچیدگی زمانی این الگوریتم چیست؟
(۰۵ مرداد ۱۳۹۴ ۰۴:۰۹ ب.ظ)NarimanN2 نوشته شده توسط:واقعا ممنون.دستتون درد نکنه(04 مرداد ۱۳۹۴ ۰۳:۰۱ ق.ظ)azbycxx نوشته شده توسط:بفرماییدNarimanN2 نوشته شده توسط: ... این سوال رو من تو تمرینات دانشگاه برکلی دیده بودم ...:سلام دوست عزیز.آیا امکانش هست این تمرینات ساختمان داده دانشگاه برکلی رو در اختیار ما هم بذارید؟
تو اینترنت گشتم،چیزی پیدا نکردم
ارسال: #۱۱
  
RE: پیچیدگی زمانی این الگوریتم چیست؟
سلام
ممنون از بابت این فایل
اما فقط یک صفحه هست این تمرینات ؟!!
مابقیش و نداری بی زحمت برامون بزاری اینجا ؟
یا لینکش رو اینجا امکان داره بزاری واسه همه ؟
ممنون از بابت این فایل
اما فقط یک صفحه هست این تمرینات ؟!!
مابقیش و نداری بی زحمت برامون بزاری اینجا ؟
یا لینکش رو اینجا امکان داره بزاری واسه همه ؟
۰
۰
ارسال: #۱۳
  
RE: پیچیدگی زمانی این الگوریتم چیست؟
خیر جز حلقه داخلی نیست چون حلقه داخلی بریس باز و بسته نداره و وقتی نداره فقط یه دستور بعد حلقه شاملش میشه
۰
ارسال: #۱۴
  
RE: پیچیدگی زمانی این الگوریتم چیست؟
باعرض سلام وخسته نباشید من توقسمت مبحث پیچیدگی ومرتبه زمانی خیلی اشکال دارم وعضومدرسان شریف هستم ازهفته آینده آزمون هایم شروع میشه خیلی استرس گرفتم تموم تست های روش تغییرمتغییروقضیه اصلی روهیچ بلدنیستم روش تغیبرمتغیرصفحه ۲۷مدرسان شریف تس های صفحه ۳۳به بعدلطفاراهنماییم کنیدباتشکر
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close