سلام

خوب اگه توی حلقه while تقسیم یا ضرب شماره گر حلقه رو داشته باشیم یعداد تکرار اون برابر log n میشه بر پایه اون عددی که درش ضرب یا بر اون تقسیم میکنیم

توی این حلقه میشه log n در مبنای ۲

(۳۰ مهر ۱۳۹۱ ۰۷:۴۸ ب.ظ)پسر کوچولوی دانشجو نوشته شده توسط:  سلام .
سوال : تعداد اجرا شدن دستور اصلی x=x+1 را در تکه برنامه زیر بدست آورید ؟
i=n
while (i>1 ) do begin
;x=x+1
; i :=i div 2
, end

بی زحمت اگه بلدین کمک کنید .

سلام دوست عزیز
بینید در حلقه while اگر عمل ضرب و یا تقسیم انجام شده بود نتیجه برابر خواهد بود Log n بر مبنای K
مثلا در این جا ; i :=i div 2 که می شود Log n بر مبنای ۲
حالا شما اگر n را ۱۶ در نظر بگیرید ،‌تعداد دفعات اجرا شدن دستور ;x=x+1 برابر ۴ خواهد بود (log 16 بر مبنای ۲)

موفق باشید .

این که خیلی راحته و از ابتدایی ترین مسائل مرتبه اجرایی الگوریتم هستش.
در کل خیلی مسائل رو میشه با تریس کردن یک ورودی و دنبال کردن تغییراتش هم بدست آورد و هم اینکه با این جور تریس کردن بیشتر تو یاد آدم می مونه.
مسلما جواب سوالتونم همونظور که بچه ها گفتن logn هستش(تمام لگاریتم ها با مبناهای متفاوت در یک مرتبه زمانی قرار دارن)

ممنون از دوستان .
میشه یه جور در حد مهدکودک توضیح بدین . گیرایی من تو این درسا خیلی خیلی ضعیفه .

سلام.قدم به قدم جلو برید.به i مقدار بدید.به ازای این مقدار حلقه یکبار اجرا میشه.بعد i=n/2 حلقه اجرا میشه و i=n/4....تا کجا پیش میره؟اگه فرض بر این بذارید که n توانی از ۲ باشه بالاخره i=1 میشه و حلقه دیگه تکرار نمیشه.
حالا باید دید کی i=1 میشه یعنی کجا مخرج کسر برابر n میشه.طبق خواص لگاریتم داریم:
a به توان (لگاریتم b در مبنای a) برابر b
پس تا جایی که مخرج برابر ۲ به توان لگاریتم n در مبنای ۲ (که برابر n هست) بشه ، این حلقه اجرا می شه.یعنی به تعداد لگاریتم n در مبنای ۲/ از آنجا که سرعت رشد تمام توابع لگاریتمی با هم برابره پس جواب میشه لگاریتم n.

ممنون .
چند تا سوال دیگه هم هست اونا رو هم میارم بعدا

دوباره سلام . سه تا سوال دیگه هست . میشه دوباره در حد مهد کودک برام حلش کنید با توضیح کامل
شرمنده همگی

سلام.واسه هر تابع برای اینکه O و یا امگا تعیین کنید اول به درجه اش دقت کنید.واسه O باید درجه ای بزرگتر یا مساوی درجه تابع انتخاب کنید.واسه امگا باید درجه ای کمتر یا مساوی تابع انتخاب کنید.یعنی O یک کران بالا و امگا یک کران پایین واسه تابع تعیین میکنن.
به نظرم یکم روش فکر کنید ببینید می تونید چیزی پیشنهاد بدید واسه هر تابع یا نه بهتر باشه.اگه نشد کمکتون می کنم.

اگه بشه خودتون حلش کنید من چیزی از این طراحی الگوریتم متوجه نمیشم .
ممنون

میشه دوستان جواب بدن سوال دوم منو ؟