سلام.
نحوه ی محاسبه کردن پیچیدگی زمانی تصویر پایین به چه صورت است:
![[تصویر: 397162_3iyednpylt33r1gdsq5m.jpg]](https://img.manesht.ir/397162_3iyednpylt33r1gdsq5m.jpg)
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
با تشگر
(۰۱ اسفند ۱۳۹۴ ۱۱:۰۸ ق.ظ)iCanDoIt نوشته شده توسط: سلام.
نحوه ی محاسبه کردن پیچیدگی زمانی تصویر پایین به چه صورت است:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
با تشگر
حالا اینها دو به دو جلوی هم گذاشته شده
اگر همش قاطی بود چی؟؟ و میگفتن از بزرگ تر به کوچک تر ، مرتب کنید چی
اولی تتا (می تونیم از هر دو عبارت سمت چپ و راست از یک ۳ فاکتور بگیریم. و عملا ۳^n عامل موثر است که در هر دو یکسان است و تنها در یک عدد ثابت ضرب شدند)
دومی امگا (وجود ضریب در توان در مرتبه موثره. توجه کنید اینجا اگه از ۳^n فاکتور بگیرید عبارت سمت راست به صورت ۳^n ضربدر ۳^(n/2-) در درمیاد که یه عامل کند کننده ۳^(n/2-) داره که سمت چپی نداره)
سومی O است (سمت راست با ساده سازی توان به صورت nlgn در میاد. سمت چپی، !n را باید به صورت ریاضی n*n-1*n-2*... بنویسید و از خاصیت تبدیل ضرب به جمع لگاریتم استفاده کنید. هر جمله سمت چپ از logn کوچکتر است و کلا هم n تا جمله داریم پس کلا از nlgn کوچکترند)
چهارمی امگا (نما بالاخره عددی بین ۱- و ۱ است. ولی n از یه جایی به بعد قطعا بزرگتر از ۲^sin n می شه)
پنجمی بستگی به a و b داره. اگر هر دو بزرگتر از یک باشن جواب امگاست (رشد تابع نمایی خیلی بیشتر از چندجمله ای هست)
آخری هم بستگی به a و b داره ولی اگر هر دو بزرگتر از یک باشن، و فرض کنیم که a مبنای لگاریتم باشه جواب O هست (رشد تابع چندجمله ای بیشتر از لگاریتمی است)
(۰۲ اسفند ۱۳۹۴ ۰۷:۵۶ ق.ظ)nobody90 نوشته شده توسط:(01 اسفند ۱۳۹۴ ۱۱:۳۸ ب.ظ)davood_2016 نوشته شده توسط: اولی تتا (می تونیم از هر دو عبارت سمت چپ و راست از یک ۳ فاکتور بگیریم. و عملا ۳^n عامل موثر است که در هر دو یکسان است و تنها در یک عدد ثابت ضرب شدند)
دومی امگا (وجود ضریب در توان در مرتبه موثره. توجه کنید اینجا اگه از ۳^n فاکتور بگیرید عبارت سمت راست به صورت ۳^n ضربدر ۳^(n/2-) در درمیاد که یه عامل کند کننده ۳^(n/2-) داره که سمت چپی نداره)
سومی O است (سمت راست با ساده سازی توان به صورت nlgn در میاد. سمت چپی، !n را باید به صورت ریاضی n*n-1*n-2*... بنویسید و از خاصیت تبدیل ضرب به جمع لگاریتم استفاده کنید. هر جمله سمت چپ از logn کوچکتر است و کلا هم n تا جمله داریم پس کلا از nlgn کوچکترند)
چهارمی امگا (نما بالاخره عددی بین ۱- و ۱ است. ولی n از یه جایی به بعد قطعا بزرگتر از ۲^sin n می شه)
پنجمی بستگی به a و b داره. اگر هر دو بزرگتر از یک باشن جواب امگاست (رشد تابع نمایی خیلی بیشتر از چندجمله ای هست)
آخری هم بستگی به a و b داره ولی اگر هر دو بزرگتر از یک باشن، و فرض کنیم که a مبنای لگاریتم باشه جواب O هست (رشد تابع چندجمله ای بیشتر از لگاریتمی است)
واسه سومی جواب "تتا " میشه.هر دو تا رو اگر به شکل بهتری قرار بدیم میشه nlogn این کاملا بدیهی ه.
بقیه درست گفتین
بله درست می گید. جواب سومی تتا هست. اثبات تتا در لینک زیر آمده است. اثبات O که بدیهی است ولی اثبات امگا به صورت استقرایی باید انجام شود:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.