سلام
اینجور سوالات من اینجور واسه خودم تحلیل میکنم حالا نمیدونم چطور میشه واسه بعضیها درست جواب میده و اسه بعضیها نه!

حلقه while بیرونی در این سوال داره هر بار بازه رو نصف میکنه یعنی log n مبنای ۲، اما این حلقه، حلقه دیگه ای از while در دل خودش داره که همون i رو این دفعه یه log n مبنای۳ دیگه میگیره ولی حاصلش بر روی حلقه بیرونی تاثیری نداره واسه همین نمیگیم log logn و لگاریتم ها در هم ضرب میشن

اگر بخوایم بگیم مبناها رو در نظر نگیریم فکر کنم گزینه ۲ باشه...

لطفا دوستان دیگه راهنمایی کنند

(۱۹ آذر ۱۳۹۱ ۰۲:۴۸ ب.ظ)Amir V نوشته شده توسط:  سلام.

دوستان تست زیر چطور حل میشه؟ و لطفا یه نفر قانون و روش حل اینطور سوالات رو توضیح بده. ممنون میشم ازتون.

کد:

for(i=0;i<n;i=i/2)
for(j=i;j<n;j=j/3)
x++;

با سلام:
به نظر من یه جای این سوال لنگ میزنه و حلقه بی نهایت بار اجرا میشه آخه شرط i=i/2 هیچ وقت افزایش پیدا نمیکنه وقتی حلقه از i=0 شروع میشه همیشه شرط برقراره/...

دوستان یه چک کنن ببینن چه جوری میشه!!!!

(۱۹ آذر ۱۳۹۱ ۰۸:۴۱ ب.ظ)m@hboobe نوشته شده توسط:  سلام
اینجور سوالات من اینجور واسه خودم تحلیل میکنم حالا نمیدونم چطور میشه واسه بعضیها درست جواب میده و اسه بعضیها نه!

حلقه while بیرونی در این سوال داره هر بار بازه رو نصف میکنه یعنی log n مبنای ۲، اما این حلقه، حلقه دیگه ای از while در دل خودش داره که همون i رو این دفعه یه log n مبنای۳ دیگه میگیره ولی حاصلش بر روی حلقه بیرونی تاثیری نداره واسه همین نمیگیم log logn و لگاریتم ها در هم ضرب میشن

اگر بخوایم بگیم مبناها رو در نظر نگیریم فکر کنم گزینه ۲ باشه...

لطفا دوستان دیگه راهنمایی کنند

با سلام:
این سوال که شما عکس اونا گذاشتین جوابش $log^{2}n$
حلقه اول $logn$ حلقه دوم هم$logn$ بار تکرار میشه در کل همون $log^{2}n$ میشه/...

منم موافقم با شما :
من اینطور تستا رو با نوشتن چند مرحله از اجراش و بعد بسطش تا آخر حل میکنم که اینطور میشه:
$log_{3}^{n} log_{3}^{n/2} log_{3}^{n/4} ... log_{3}^{2} log_{3}^{1}$
که تعداد این log ها برابر با$log_{2}^{n}$
و از اونجایی که تمام log ها با هم هم رشد هستند برای تعیین مرتبه میتونیم پایه log ها رو ۲ در نظر بگیرم و بگیم که lg n تا lg داریم(n و n/2 و ... رو هم میتونیم همرو n در نظر بگیریم).
که میشه : $\Theta (lgn lgn lgn ...)=\Theta(lg^2n)$

(۱۹ آذر ۱۳۹۱ ۰۹:۱۹ ب.ظ)deh-ab نوشته شده توسط:  به نظر من یه جای این سوال لنگ میزنه و حلقه بی نهایت بار اجرا میشه آخه شرط i=i/2 هیچ وقت افزایش پیدا نمیکنه وقتی حلقه از i=0 شروع میشه همیشه شرط برقراره/...

دوستان یه چک کنن ببینن چه جوری میشه!!!!

بله همین جوره که میگید !
من تستهای سال۹۱ کامپیوتر و ایتی چک کردم فقط این سوال بود که چنین شباهتی داشت با این تیکه کد!!

ممنون بچه ها.

یه دفعه دیگه میشه بگین چرا loglogn نمیشه؟

منبعی یا جزوه ای چیزی دارین که بشه این نوع مرتبه زمانیها رو از روش خوند؟ یا مثلا مرتبه زمانیهایی که نیاز به تغییر متغیر دارن.

Sent from my Google Galaxy Nexus using Tapatalk 2.4

(۱۹ آذر ۱۳۹۱ ۱۰:۲۲ ب.ظ)Amir V نوشته شده توسط:  ممنون بچه ها.

یه دفعه دیگه میشه بگین چرا loglogn نمیشه؟

منبعی یا جزوه ای چیزی دارین که بشه این نوع مرتبه زمانیها رو از روش خوند؟ یا مثلا مرتبه زمانیهایی که نیاز به تغییر متغیر دارن.

Sent from my Google Galaxy Nexus using Tapatalk 2.4

ببینید داخل تمام حل هایی که دوستان انجام دادند ثابت شد که ما به تعداد lgn بار حلقه شامل حلقه داخلی (که خود حلقه داخلی هم تقریبا هر بار lgn بار اجرا میشه) رو اجرا میکنیم پس lgn * lgn جواب میشه. اما lglgn رشدش خیلی کمتر از این حرفاست، هیچ ربطی به جواب این سوال نداره دلیل سوالتون رو نمیفهمم، جایی همچین جوابی دادند که واسه شما سوال شده؟
البته گاهی دیدم برخی این ۲ تا رو به اشتباه(بخاطر نزدیکی ظاهری) یکی میدونن ، اما با کمی توجه میفهمید که خیییییلی با هم فرق دارند!

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

درسته. بابت گیج بازیم شرمنده.
مرسی.

Sent from my Google Galaxy Nexus using Tapatalk 2.4