سلام همگی
من تازه این ترم ساختمون داده برداشتم واسه همین خیلی گیج شدم تو خیلی چیزا.اگه میشه کمک کنید
میشه یکی با اثبات بهم بگه چرا بیگoالگوریتم ضرب ماتریسn*nمیشه n^3
و واسه دودویی میشه lognدر مبنای ۲؟
خواهش میکنم راهنماییم کنید
سلام ضرب ماتریسا که تتای n^3 میشه نه بیگ اُی n^3!
در مورد سوال دومتونم منظورتونو دقیق متوجه نشدم اما اگه منظورتون اینه کلا جستجوی دودویی چرا logn هست خب دلیلش ساختاریه که درخت جستجوی دودویی داره . ساختار درخت به این شکل هست که فرزندان چپ ریشه از ریشه کوچکتر و فرزندان راست از ریشه بزرگتر هستن . همچنین هر فرزند هم این خاصیت رو داره . بنابراین وقتی که مثلا عدد ۲۳ داده بشه با ریشه مقایسه میشه اگه از ریشه کوچکتر بود ادامه ی جستجو در زیر درخت چپ انجام میشه و اگه بزرگتر بود در زیر درخت راست . اگه هم مساوی بود که واضحه دیگه ....
خب حالا ما به جای اینکه کل نودهای درخت رو بگردیم در هر مرحله به طور متوسط داریم نصفشونو میگردیم .
و در هر مرحله تعداد نودهایی که باید بگردیم نصف میشه و نصف میشه و ...
به طور کلی این الگوریتم بیگ اُی (k) هست که k ارتفاع درخت ما میشه . اما در بدترین حالت ارتفاع درخت برابر تعداد نودهای ما میشه و الگوریتم بیگ اُی n میشه( وقتی درخت مورب باشه) و در بهترین حالت ارتفاع درخت logn هستش و الگوریتم بیگ اُی logn میشه (یعنی وقتی که درخت تقریبا متعادل باشه ).
مسلما راهی فرمولی هست واسه اثبات اینکه چرا پیچیدگی زمانی الگوریتم ضرب دو ماتریس n*nمیشه N^3.نیس؟
(۰۶ مهر ۱۳۹۲ ۰۵:۱۵ ب.ظ)nazanin2013 نوشته شده توسط: مسلما راهی فرمولی هست واسه اثبات اینکه چرا پیچیدگی زمانی الگوریتم ضرب دو ماتریس n*nمیشه N^3.نیس؟بله من فکر کردم مشکلتون با قسمت بیگ اُ بودنشه
این مسءله نیاز به روش پویا داره . اگه کتاب طراحی الگوریتم پارسه رو دارید فصل برنامه نویسی پویا مسءله ضرب ماتریس ها رو بخونید به طور کامل توضیح داده شده . اگه نه بفرمایید تا توضیح بدم
(۰۶ مهر ۱۳۹۲ ۰۵:۴۳ ب.ظ)nazanin_sh نوشته شده توسط:نه ندارم .اگه توضیح بدین که ممنون میشم.ببخشید(06 مهر ۱۳۹۲ ۰۵:۱۵ ب.ظ)nazanin2013 نوشته شده توسط: مسلما راهی فرمولی هست واسه اثبات اینکه چرا پیچیدگی زمانی الگوریتم ضرب دو ماتریس n*nمیشه N^3.نیس؟بله من فکر کردم مشکلتون با قسمت بیگ اُ بودنشه
این مسءله نیاز به روش پویا داره . اگه کتاب طراحی الگوریتم پارسه رو دارید فصل برنامه نویسی پویا مسءله ضرب ماتریس ها رو بخونید به طور کامل توضیح داده شده . اگه نه بفرمایید تا توضیح بدم
(۰۶ مهر ۱۳۹۲ ۰۵:۱۵ ب.ظ)nazanin2013 نوشته شده توسط: مسلما راهی فرمولی هست واسه اثبات اینکه چرا پیچیدگی زمانی الگوریتم ضرب دو ماتریس n*nمیشه N^3.نیس؟
الگوریتم ضرب ماتریس های n*n به صورت ۳ حلقه ی for تودرتو نوشته میشه
به ازای هر for تو در تو یه n . پس ۳ تا for تودر تو میشه : n*n*n که برابره با n^3