سلام دوستان
به نظرشما این سوال چطوری میشه حل کرد
T(n)=2T(n/2)+n/logn
هر موقع لگاریتم میره تو مخرج من نمی دونم دقیقا باید از چه روشی حل کنم
اگر به روش درختی بخوایم حلش کنیم توی ارتفاع درخت گیر میکنم و نمیدونم ارتفاع از کجا بدست بیارم
از روش master هم باز گیر میکنم
با توجه به روش master: مقدار n به توان loga در مبنای b میشه n
و n/logn=o(n)
پس مرتبه t(n) میشه همون n
درسته دوستان؟
توی جوابش نوشته
(teta(nlglgn
ولی راه حل تشریحی نداره
من فکر میکنم باید تغییر متغیر بدیم مثلا m=logn و n=2^m و .... البته خودم حل نکردم ببینم جواب میده یا نه!
(۱۸ دى ۱۳۸۹ ۰۲:۵۹ ب.ظ)afagh1389 نوشته شده توسط: من فکر میکنم باید تغییر متغیر بدیم مثلا m=logn و n=2^m و .... البته خودم حل نکردم ببینم جواب میده یا نه!
من از این روش رفتم نتونستم جواب بگیرم
میشه: S(m)= 2S(m-1) + 2^m/m
با این جمله می تونیم به جایی برسیم؟
نه دوستان
از master استفاده نکنید.
لطفا به نکته ای که تو نکات طراحی گذاشتم نگاه کنید.
معلومه اصلا نکاتو نمیخونید. نومید شدم.
من درختی حل کردم و به جواب رسیدم .
الان وقت ندارم بزارم.
آره راست می گید
بی دقتی کردم
راستش تا نصف این نکات را بیشتر نخوندم!!
ممنون که تذکر دادید.
راه اول:
راه حل اصلی که استفاده از درخت بازگشت هست که این مثال دقیقا توی کتاب پوران هم هست.همیشه برای بدست اوردن ارتفاع می بینیم تابع بازگشتیمون مثلا تقسیم بر k شده ارتفاعمون پس میشه لگاریتم n درمبنای K.اگر بر دو عدد متفاوت تقسیم شده بود مثلا بود t(n/4)+t(n/3 در این صورت K را عدد کوچکتر میگیریم(۳) زیرا دیرتر اون قسمت درخت به برگ میرسه.
پس توی این سوال ارتفاع میشه Lgn.حالا باید مقادیر هر سطح رو جمع بزنید.
سطح اول: n/lgn
سطح دوم: n تقسیم بر لگاریتم n دوم= n/lgn-1
سطح سوم: n/lgn-2
....
پس جوابمون میشه مجموع این سطوح که تا ارتفاع lgn ادامه دارند:
[tex]n(1/lg n 1/((lg n)-1) ...1/2 1)[/tex]
{قسمت داخل پرانتز اگر n بجای Lgn بود میشد تتای lgn پس حالا میشه تتای lglgn.در نتیجه جواب میشه:تتای nlglgn
راه دوم:
از قضیه اصلی و قضیه اصلی تعمیم یافته نمی شه توی این مساله استفاده کرد ولی یک قضیهی دیگه وجود دارد که شامل اکثر حالات میشه و می تونید از اون استفاده کنید.قضیه مورد نظر را توی یکی از کتابای گسسته که تو گوگل بوک بود دیدم و توی کتاب های کنکوری و مرجع خودمون نیست.
یکی از حالات این قضیه هست که میگه در صورتی که توان n در دو طرف یکی شد و لگاریتم هم توان منفی یک داشت جواب در lglgn ضرب خواهد شد.
(۱۸ دى ۱۳۸۹ ۰۳:۲۷ ب.ظ)حامد نوشته شده توسط: راه اول:سلام
راه حل اصلی که استفاده از درخت بازگشت هست که این مثال دقیقا توی کتاب پوران هم هست.همیشه برای بدست اوردن ارتفاع می بینیم تابع بازگشتیمون مثلا تقسیم بر k شده ارتفاعمون پس میشه لگاریتم n درمبنای K.اگر بر دو عدد متفاوت تقسیم شده بود مثلا بود t(n/4)+t(n/3 در این صورت K را عدد کوچکتر میگیریم(۳) زیرا دیرتر اون قسمت درخت به برگ میرسه.
پس توی این سوال ارتفاع میشه Lgn.حالا باید مقادیر هر سطح رو جمع بزنید.
سطح اول: n/lgn
سطح دوم: n تقسیم بر لگاریتم n دوم= n/lgn-1
سطح سوم: n/lgn-2
....
پس جوابمون میشه مجموع این سطوح که تا ارتفاع lgn ادامه دارند:
[tex]n(1/lg n 1/((lg n)-1) ...1/2 1)[/tex]
{قسمت داخل پرانتز اگر n بجای Lgn بود میشد تتای lgn پس حالا میشه تتای lglgn.در نتیجه جواب میشه:تتای nlglgn
راه دوم:
از قضیه اصلی و قضیه اصلی تعمیم یافته نمی شه توی این مساله استفاده کرد ولی یک قضیهی دیگه وجود دارد که شامل اکثر حالات میشه و می تونید از اون استفاده کنید.قضیه مورد نظر را توی یکی از کتابای گسسته که تو گوگل بوک بود دیدم و توی کتاب های کنکوری و مرجع خودمون نیست.
یکی از حالات این قضیه هست که میگه در صورتی که توان n در دو طرف یکی شد و لگاریتم هم توان منفی یک داشت جواب در lglgn ضرب خواهد شد.
شما توی کدوم کتاب این قضیه رو دیدید؟
(۱۸ دى ۱۳۸۹ ۰۹:۴۶ ب.ظ)بی رنگ نوشته شده توسط: سلامکتاب ساختمان های گسسته،منطق و محاسبات نوشته پروفسور Hein.کتاب رو نخوندم توی گوگل سرچ زده بودم یک صفحه از کتاب ایشون رو پیدا کرد.و همان طور که گفتم با قضیه مستر فرق میکنه.
شما توی کدوم کتاب این قضیه رو دیدید؟
اگر لازم می دونید بگید تا یه Search بزنم و اینجا بزارمش.
(۱۸ دى ۱۳۸۹ ۰۳:۲۷ ب.ظ)حامد نوشته شده توسط: راه اول:
سطح اول: n/lgn
سطح دوم: n تقسیم بر لگاریتم n دوم= n/lgn-1
سطح سوم: n/lgn-2
....
پس جوابمون میشه مجموع این سطوح که تا ارتفاع lgn ادامه دارند:
[tex]n(1/lg n 1/((lg n)-1) ...1/2 1)[/tex]
{قسمت داخل پرانتز اگر n بجای Lgn بود میشد تتای lgn پس حالا میشه تتای lglgn.در نتیجه جواب میشه:تتای nlglgn
راه دوم:
من استفاده از درخت بازگشت برای حل اینگونه مسائل را خیلی بلد نیستم
میشه یکی لطف کنه فرمول بالا را واضحتر توضیح بده؟؟
مثلا چرا سطح دوم شده n تقسیم بر لگاریتم n دوم؟ مگه نباید n/2 تقسیم بر لگاریتم n/2 باشه؟
(۱۹ دى ۱۳۸۹ ۰۲:۴۴ ق.ظ)ali نوشته شده توسط: اگر امکانش هست لینکش رو بگذارید
مرسی.
صورت کامل قضیه که از کتاب مورد نظر عکسشو گرفتم:
[attachment=260]
(۱۹ دى ۱۳۸۹ ۱۱:۳۰ ق.ظ)zr2358 نوشته شده توسط: من استفاده از درخت بازگشت برای حل اینگونه مسائل را خیلی بلد نیستممتاسفانه من بیانم برای توضیح این موارد خوب نیست!بیشتر از اینکه خود مساله رو توضیح بدم به جزییاتش میپردازم.امیدوارم که بقیه دوستان که بهتر می تونند توضیح بدند کمکتون کنند.ولی در مورد سوالتون:
میشه یکی لطف کنه فرمول بالا را واضحتر توضیح بده؟؟
مثلا چرا سطح دوم شده n تقسیم بر لگاریتم n دوم؟ مگه نباید n/2 تقسیم بر لگاریتم n/2 باشه؟
توی سطح دوم دو تا گره داریم چون توی صورت سوال داشتیم ۲t(n/2 .هر کدومشون مقدارش میشه n/2 تقسیم بر لگاریتم n/2 که جمعشون میشه n تقسیم بر لگاریتم n دوم.
(۲۰ دى ۱۳۸۹ ۰۲:۰۹ ب.ظ)yasemi نوشته شده توسط: آقا حامد این عکس مال چه کتابی هست ؟صفحهی قبلی رو نخوندید؟گفتم که!کتاب ساختمان های گسسته،منطق و محاسبات نوشته پروفسور Hein
کلا قضیهی خوبیه.فقط طراحها نفهمند که همچین قضیه ای وجود داره که کار خراب میشه!
توی صفحهی بعدش هم چند تا مثال ازش نوشته به شکل زیر:
[attachment=261]
(۲۱ دى ۱۳۸۹ ۱۲:۲۵ ب.ظ)yasemi نوشته شده توسط: حامد جان اگه میشه لیک شو بزار باید کتاب جالبی باشه . راستی ما تو رو نداشتیم چکار میکردیم
لینک مربوط به گوگل بوک:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
توی تمرین های همین بخش هم یه ۲۰ تا سوالی داره که چند تاییشون بد نیستند.(از صفحهی ۳۸۹)
بقیهی سرفصل هاشو که میدیدم مورد جالبی پیدا نکردم.حالا شما هم ببینید اگر چیزی بود آدرسشو بدید.