۲
subtitle
ارسال: #۱
مقایسه ی رشد دو تابع
سلام دوستان
رشد کدوم بیشتره؟
[tex]n^{0.999999}\times\log n[/tex] یا [tex]10000000\times n[/tex]?
اگه طرفین را ساده کنیم از یه طرف [tex]10000000\times n^{0.000001}[/tex] میمونه و از طرف دیگه log n . ولی من نمیدونم کدوم بزرگتره.
ممنون
رشد کدوم بیشتره؟
[tex]n^{0.999999}\times\log n[/tex] یا [tex]10000000\times n[/tex]?
اگه طرفین را ساده کنیم از یه طرف [tex]10000000\times n^{0.000001}[/tex] میمونه و از طرف دیگه log n . ولی من نمیدونم کدوم بزرگتره.
ممنون
۲
ارسال: #۲
RE: مقایسه ی رشد دو تابع
از نظر مربته زمانی
[tex]n^{\epsilon}>\log n[/tex]
حالا این [tex]\epsilon[/tex] می خواد یه عدد خیییییییییییییییییلی کوچیک باشه یا یه عدد بزرگ
حالا اگه [tex]\epsilon[/tex] رو ۰/۰۰۰۰۰۱ در نظر بگیریم:
[tex]n^{0.000001}>\log n[/tex]
و اگر طرفین رو در [tex]n^{0.999999}[/tex] ضرب کنیم داریم:
[tex]n>n^{0.999999}\log n[/tex]
و واضحه که اون ضریب ثابت ۱۰۰۰۰۰۰۰ در سمت چپ تاثیری در مرتبه زمانی نداره (چون ثابته)
فقط نکته ش اینه که یه چند جمله ای با هر توانی (هر چند خیییییییییییییلی کوچک) همواره مرتبه ی بیشتری نسبت به یک لگاریتم با هر توانی ( هر چند خییییییییلی بزرگ) دارد.
[tex]n^{\epsilon}>\log n[/tex]
حالا این [tex]\epsilon[/tex] می خواد یه عدد خیییییییییییییییییلی کوچیک باشه یا یه عدد بزرگ
حالا اگه [tex]\epsilon[/tex] رو ۰/۰۰۰۰۰۱ در نظر بگیریم:
[tex]n^{0.000001}>\log n[/tex]
و اگر طرفین رو در [tex]n^{0.999999}[/tex] ضرب کنیم داریم:
[tex]n>n^{0.999999}\log n[/tex]
و واضحه که اون ضریب ثابت ۱۰۰۰۰۰۰۰ در سمت چپ تاثیری در مرتبه زمانی نداره (چون ثابته)
فقط نکته ش اینه که یه چند جمله ای با هر توانی (هر چند خیییییییییییییلی کوچک) همواره مرتبه ی بیشتری نسبت به یک لگاریتم با هر توانی ( هر چند خییییییییلی بزرگ) دارد.
۰
ارسال: #۳
RE: مقایسه ی رشد دو تابع
به گمانم ...
همواره رشد چندجمله‌ای به رشد Polylogarithmic چیره می‌شود و آمیختن Polylogarithmic با چندچمله‌ای توسط ضرب، سبب تغییر توانی در رشد آن چندجمله‌ای نمی‌شود. در بین چندجمله‌ای‌ها هم فارغ از بزرگی ضرایب، آن که با epsilon تفاوت در توانش، بزرگتر است، یک کلاس پیچیدگی بالاتر تشکیل می‌دهد.
در حل مسئله فوق به روش لگاریتم‌گیری از دو طرف، به این ادعا رسیدم:
اگر دو مسئله با رشد Polylogarithmic داشته باشیم، آن که دارای ضریب ثابت بیشتری است - بر خلاف محاسبات مجانبی روی پیچیدگی های چندجمله‌ای یا بالاتر - یک کلاس پیچیدگی بالاتر را تشکیل می‌دهد.
امیدوارم کسی پیدا بشه که بتونه اثبات یا ردش کنه.
همواره رشد چندجمله‌ای به رشد Polylogarithmic چیره می‌شود و آمیختن Polylogarithmic با چندچمله‌ای توسط ضرب، سبب تغییر توانی در رشد آن چندجمله‌ای نمی‌شود. در بین چندجمله‌ای‌ها هم فارغ از بزرگی ضرایب، آن که با epsilon تفاوت در توانش، بزرگتر است، یک کلاس پیچیدگی بالاتر تشکیل می‌دهد.
در حل مسئله فوق به روش لگاریتم‌گیری از دو طرف، به این ادعا رسیدم:
اگر دو مسئله با رشد Polylogarithmic داشته باشیم، آن که دارای ضریب ثابت بیشتری است - بر خلاف محاسبات مجانبی روی پیچیدگی های چندجمله‌ای یا بالاتر - یک کلاس پیچیدگی بالاتر را تشکیل می‌دهد.
امیدوارم کسی پیدا بشه که بتونه اثبات یا ردش کنه.
ارسال: #۴
RE: مقایسه ی رشد دو تابع
(۲۶ مهر ۱۳۹۳ ۰۵:۴۰ ب.ظ)MShariati نوشته شده توسط: به گمانم ...
همواره رشد چندجمله‌ای به رشد Polylogarithmic چیره می‌شود و آمیختن Polylogarithmic با چندچمله‌ای توسط ضرب، سبب تغییر توانی در رشد آن چندچمله‌ای نمی‌شود. در بین چندجمله‌ای‌ها هم فارغ از بزرگی ضرایب، آن که با epsilon تفاوت در توانش بزرگتر است، یک کلاس پیچیدگی بالاتر تشکیل می دهد.
بله من لفظا اشتباه گفتم.همون لگاریتم گیری از طرفین درسته
فکر کنم سوال رو اشتباه حل کرده بودم الان که دوباره حل کردم بله فکر کنم حق با شماست
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close