سلام ضرب ماتریسا که تتای 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