سوال: مرتبه اجرایی عبارات زیر چیست؟ [بایگانی]

veniz2008

جمعه 25 آذر 1390, 23:29 عصر

سلام دوستان،مرتبه اجرایی( big-O ) عبارات زیر چی میشه؟

n^3 + Log(n!) +n
و
n + 2^Log(n!) +2^n

در مورد اولی خودم فکر میکنم که در نهایت n^3 بزرگتر میشه و جواب سوال هست ولی شک دارم،آیا روش تشریحی برای حل مسائلی به این شکل وجود داره؟،هر کدوم از دوستان که جواب ها رو میدونن لطفا یک پاسخ کامل ارائه بده،تشکر.

مسعود اقدسی فام

یک شنبه 27 آذر 1390, 00:28 صبح

سلام دوستان،مرتبه اجرایی( big-O ) عبارات زیر چی میشه؟

n^3 + Log(n!) +n
و
n + 2^Log(n!) +2^n

در مورد اولی خودم فکر میکنم که در نهایت n^3 بزرگتر میشه و جواب سوال هست ولی شک دارم،آیا روش تشریحی برای حل مسائلی به این شکل وجود داره؟،هر کدوم از دوستان که جواب ها رو میدونن لطفا یک پاسخ کامل ارائه بده،تشکر.

اولی n به توان سه و دومی دو به توان لگاریتم !n.

مسعود اقدسی فام

یک شنبه 27 آذر 1390, 00:33 صبح

سلام دوستان،مرتبه اجرایی( big-O ) عبارات زیر چی میشه؟

n^3 + Log(n!) +n
و
n + 2^Log(n!) +2^n

در مورد اولی خودم فکر میکنم که در نهایت n^3 بزرگتر میشه و جواب سوال هست ولی شک دارم،آیا روش تشریحی برای حل مسائلی به این شکل وجود داره؟،هر کدوم از دوستان که جواب ها رو میدونن لطفا یک پاسخ کامل ارائه بده،تشکر.

مثلا مقایسه دو به توان n و دو به توان !log n رو مقایسه n و !log n در نظر بگیرید. این دو معادل مقایسه ده به توان n و !n هستن (اگه پایه‌ی لگاریتم رو ده فرض کنیم). همونطور که می‌دونید تمام عبارات چند جمله‎ای برای nهای به اندازه کافی بزرگ زیر !n هستن. پس در کل n زیر !log n هست و همینطور تا آخر. پایه‌ی لگاریتم هم اصلا مهم نیست چند در نظر گرفته بشه.

veniz2008

یک شنبه 27 آذر 1390, 11:10 صبح

مثلا مقایسه دو به توان n و دو به توان !log n رو مقایسه n و !log n در نظر بگیرید. این دو معادل مقایسه ده به توان n و !n هستن (اگه پایه‌ی لگاریتم رو ده فرض کنیم). همونطور که می‌دونید تمام عبارات چند جمله‎ای برای nهای به اندازه کافی بزرگ زیر !n هستن. پس در کل n زیر !log n هست و همینطور تا آخر. پایه‌ی لگاریتم هم اصلا مهم نیست چند در نظر گرفته بشه.
ضمن تشکر از پاسخ شما،اگه واسه همین قسمت دوم داشته باشیم: دو به توان nبه توان2، اونوقت در مقایسه بین ده به توان nبه توان2 و !n ،کدومشون بزرگتر میشه؟،برای چنین حالاتی میشه تحلیل خاصی رو بکار برد یا بهتره که با عدد گذاری به نتیجه رسید؟

مسعود اقدسی فام

یک شنبه 27 آذر 1390, 22:09 عصر

ضمن تشکر از پاسخ شما،اگه واسه همین قسمت دوم داشته باشیم: دو به توان nبه توان2، اونوقت در مقایسه بین ده به توان nبه توان2 و !n ،کدومشون بزرگتر میشه؟،برای چنین حالاتی میشه تحلیل خاصی رو بکار برد یا بهتره که با عدد گذاری به نتیجه رسید؟

بهترین تحلیل همون تعریف ریاضی O هست که البته گاهی پیچیده می‌شه.