(۱۱ بهمن ۱۳۹۳ ۰۹:۴۶ ب.ظ)enayati.amirhossein نوشته شده توسط:  دوستان لطفا این سوال رو حل کنید. فک میکنم راه حل کتاب پوران پژوهش اشتباه هست البته گزینه انتخاب شده صحیحه.
for(i=1;i<=n;i++)
for(j=1;j<=n;j=j+i)
x++;

جواب : nlogn
ممنون میشم اگه توضیح بدید[/align]

سلام
یکی یکی به i مقدار میدیم ببینیم به ازای هر مقدار حلقه j چند بار اجرا میشه
وقتیi=1 باشه مقدار j یکی یکی زیاد میشه و در نتیجه nبار این حلقه اجرا میشه
وقتیi=2باشه حلقه جی n/2 بار اجرا میشه
وقتیi=3باشه حلقه جی n/3بار اجرا میشه
.
.
.
وقتی i=n باشه حلقه جی ۱بار اجرا میشه
اگر همه تکرارهای بالارو جمع کنید (n+n/2+n/3+...+1) و بعدش از n فاکتور بگیرید => n.sigma 1/i= nlogn
حدود سیگما از ۱ تا n هست
موفق باشید

(۱۱ بهمن ۱۳۹۳ ۱۰:۵۶ ب.ظ)afrooz-OMD نوشته شده توسط:  

(11 بهمن ۱۳۹۳ ۰۹:۴۶ ب.ظ)enayati.amirhossein نوشته شده توسط:  دوستان لطفا این سوال رو حل کنید. فک میکنم راه حل کتاب پوران پژوهش اشتباه هست البته گزینه انتخاب شده صحیحه.
for(i=1;i<=n;i++)
for(j=1;j<=n;j=j+i)
x++;

جواب : nlogn
ممنون میشم اگه توضیح بدید[/align]

سلام
یکی یکی به i مقدار میدیم ببینیم به ازای هر مقدار حلقه j چند بار اجرا میشه
وقتیi=1 باشه مقدار j یکی یکی زیاد میشه و در نتیجه nبار این حلقه اجرا میشه
وقتیi=2باشه حلقه جی n/2 بار اجرا میشه
وقتیi=3باشه حلقه جی n/3بار اجرا میشه
.
.
.
وقتی i=n باشه حلقه جی ۱بار اجرا میشه
اگر همه تکرارهای بالارو جمع کنید (n+n/2+n/3+...+1) و بعدش از n فاکتور بگیرید => n.sigma 1/i= nlogn
حدود سیگما از ۱ تا n هست
موفق باشید

دقیقا مشکلم همین جاست اگه n=4 باشه اون وقت این قضیه که گفتید در i=3 تعداد تکرار حلقه j برابر n/3 هست صادق نیست مگر به بالا گرد بشه. میشه بررسی کنید. ممنون میشم

(۱۲ بهمن ۱۳۹۳ ۱۲:۰۷ ب.ظ)enayati.amirhossein نوشته شده توسط:  

(11 بهمن ۱۳۹۳ ۱۰:۵۶ ب.ظ)afrooz-OMD نوشته شده توسط:  

(11 بهمن ۱۳۹۳ ۰۹:۴۶ ب.ظ)enayati.amirhossein نوشته شده توسط:  دوستان لطفا این سوال رو حل کنید. فک میکنم راه حل کتاب پوران پژوهش اشتباه هست البته گزینه انتخاب شده صحیحه.
for(i=1;i<=n;i++)
for(j=1;j<=n;j=j+i)
x++;

جواب : nlogn
ممنون میشم اگه توضیح بدید[/align]

سلام
یکی یکی به i مقدار میدیم ببینیم به ازای هر مقدار حلقه j چند بار اجرا میشه
وقتیi=1 باشه مقدار j یکی یکی زیاد میشه و در نتیجه nبار این حلقه اجرا میشه
وقتیi=2باشه حلقه جی n/2 بار اجرا میشه
وقتیi=3باشه حلقه جی n/3بار اجرا میشه
.
.
.
وقتی i=n باشه حلقه جی ۱بار اجرا میشه
اگر همه تکرارهای بالارو جمع کنید (n+n/2+n/3+...+1) و بعدش از n فاکتور بگیرید => n.sigma 1/i= nlogn
حدود سیگما از ۱ تا n هست
موفق باشید

دقیقا مشکلم همین جاست اگه n=4 باشه اون وقت این قضیه که گفتید در i=3 تعداد تکرار حلقه j برابر n/3 هست صادق نیست مگر به بالا گرد بشه. میشه بررسی کنید. ممنون میشم

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