سلام دوستان
رشد کدوم بیشتره؟
[tex]n^{0.999999}\times\log n[/tex] یا [tex]10000000\times n[/tex]?
اگه طرفین را ساده کنیم از یه طرف [tex]10000000\times n^{0.000001}[/tex] میمونه و از طرف دیگه log n . ولی من نمیدونم کدوم بزرگتره.
ممنون
ممنون از پاسختون
(۲۴ مهر ۱۳۹۳ ۰۶:۵۵ ب.ظ)miladcr7 نوشته شده توسط: سلام.برای مقایسه از طرفین لگاریتم بگیرید میبینید که ۱۰۰۰۰۰۰۰n بزرگترهچطوری از طرفین لگاریتم گرفتید؟
(۲۶ مهر ۱۳۹۳ ۰۳:۳۷ ب.ظ)Ametrine نوشته شده توسط:(24 مهر ۱۳۹۳ ۰۶:۵۵ ب.ظ)miladcr7 نوشته شده توسط: سلام.برای مقایسه از طرفین لگاریتم بگیرید میبینید که ۱۰۰۰۰۰۰۰n بزرگترهچطوری از طرفین لگاریتم گرفتید؟
از سمت چپ دو طرف رو در لگاریتم ضرب کنید یکی میشه ۱۰۰۰۰۰۰۰logn و اون یکیش هم میشه ۰/۹۹۹۹۹۹logn*logn که الان توی این دو تابع logn ها دارای رشد یکسان هستند ولی ۰/۹۹۹۹۹۹logn نزولی هستش و ۱۰۰۰۰۰۰۰ تابع ثابت که برای n های بزرگ رشدش از ۱۰۰۰۰۰۰۰logn بیشتره
پس در نتیجه رشد ۱۰۰۰۰۰۰۰logn بیشتره
به گمانم ...
همواره رشد چندجمله‌ای به رشد Polylogarithmic چیره می‌شود و آمیختن Polylogarithmic با چندچمله‌ای توسط ضرب، سبب تغییر توانی در رشد آن چندجمله‌ای نمی‌شود. در بین چندجمله‌ای‌ها هم فارغ از بزرگی ضرایب، آن که با epsilon تفاوت در توانش، بزرگتر است، یک کلاس پیچیدگی بالاتر تشکیل می‌دهد.
در حل مسئله فوق به روش لگاریتم‌گیری از دو طرف، به این ادعا رسیدم:
اگر دو مسئله با رشد Polylogarithmic داشته باشیم، آن که دارای ضریب ثابت بیشتری است - بر خلاف محاسبات مجانبی روی پیچیدگی های چندجمله‌ای یا بالاتر - یک کلاس پیچیدگی بالاتر را تشکیل می‌دهد.
امیدوارم کسی پیدا بشه که بتونه اثبات یا ردش کنه.
(۲۶ مهر ۱۳۹۳ ۰۶:۴۷ ب.ظ)Ametrine نوشته شده توسط:بله همینجوره.اون قسمتی هم که دو لگاریتم داره به این خاطر اونشکلی شده که میشه (logn*log(n^0.999999 همونجوری که دقت کنی الان توان برای n هستش که توان رو پشت لگاریتم میبریم و اون شکلی میشه خب!!!!(26 مهر ۱۳۹۳ ۰۵:۱۷ ب.ظ)miladcr7 نوشته شده توسط:یعنی log رو در دو طرف ضرب میکنیم دیگه؟(26 مهر ۱۳۹۳ ۰۳:۳۷ ب.ظ)Ametrine نوشته شده توسط:(24 مهر ۱۳۹۳ ۰۶:۵۵ ب.ظ)miladcr7 نوشته شده توسط: سلام.برای مقایسه از طرفین لگاریتم بگیرید میبینید که ۱۰۰۰۰۰۰۰n بزرگترهچطوری از طرفین لگاریتم گرفتید؟
از سمت چپ دو طرف رو در لگاریتم ضرب کنید یکی میشه ۱۰۰۰۰۰۰۰logn و اون یکیش هم میشه ۰/۹۹۹۹۹۹logn*logn که الان توی این دو تابع logn ها دارای رشد یکسان هستند ولی ۰/۹۹۹۹۹۹logn نزولی هستش و ۱۰۰۰۰۰۰۰ تابع ثابت که برای n های بزرگ رشدش از ۱۰۰۰۰۰۰۰logn بیشتره
پس در نتیجه رشد ۱۰۰۰۰۰۰۰logn بیشتره
که میشن ۱۰۰۰۰۰۰۰logn و ۰/۹۹۹۹۹۹log*logn
چون شما نوشتید ۰/۹۹۹۹۹۹logn*logn
یعنی logn رو ضرب کردید؟
اگه log رو ضرب کنیم که دیگه واضح هست که ۰/۹۹۹۹۹۹log*logn کوچیکتره.
(۲۶ مهر ۱۳۹۳ ۰۷:۳۶ ب.ظ)miladcr7 نوشته شده توسط: بله همینجوره.اون قسمتی هم که دو لگاریتم داره به این خاطر اونشکلی شده که میشه (logn*log(n^0.999999 همونجوری که دقت کنی الان توان برای n هستش که توان رو پشت لگاریتم میبریم و اون شکلی میشه خب!!!!آهان، ببخشید حواسم نبود که اون توان بوده.
نقل قول: ولی ۰/۹۹۹۹۹۹logn نزولی هستشمن ریاضیم زیاد خوب نیست ولی به نظرم ادعای فوق اشتباهه.
ضمناً اگه از دو طرف لگاریتم بگیریم، نتیجه میشه:
۷lg10 + lgn (طرف اول)
۰/۹۹۹۹۹۹lgn + lglgn (طرف دوم)
مطمئن نیستم ولی به نظرم در محاسبات مجانبی Polylogarithmic بر خلاف محاسبات با پیچیدگی چندچمله ای یا بیشتر، بزرگی ضریب ثابت اهمیت داره. که اگه این درست باشه، به نتیجه دلخواه رسیدیم.
عذر می‌خوام! من فقط لگاریتم گیری بلدم و اصلاً نمی‌فهمم ضرب کردن در لگاریتم به چه مفهومه!!!
در مورد نزولی بودن هم قبلاً گفتم که کلاً قبولش ندارم، شما مطمئنید که اون عبارت به ازای افزایش n مقادیرش نزولی میشه؟!
(۲۸ مهر ۱۳۹۳ ۰۸:۱۹ ق.ظ)MShariati نوشته شده توسط: عذر می‌خوام! من فقط لگاریتم گیری بلدم و اصلاً نمی‌فهمم ضرب کردن در لگاریتم به چه مفهومه!!!
در مورد نزولی بودن هم قبلاً گفتم که کلاً قبولش ندارم، شما مطمئنید که اون عبارت به ازای افزایش n مقادیرش نزولی میشه؟!
بله شما درست میفرمایید.
من لفظا اشتباه گفتم.توی پست اولمم گفتم که از طرفین لگاریتم میگیریم.الان تصحیحش میکنم.میشه بپرسم چجوری لگاریتم گرفتید که به اون حالت رسیدید؟؟؟؟(۲۸ مهر ۱۳۹۳ ۰۹:۲۸ ق.ظ)Aurora نوشته شده توسط: منظورتون چیه از اینکه در لگاریتم ضرب می کنیم؟ مگه همچین چیزی داریم؟
می تونیم از دو طرف لگاریتم بگیریم نه اینکه در لگاریتم ضرب کنیم.
در مورد نزولی بودن که به نظرم اشتباهه. همچنین مقایسه یک تابع با یک عدد ثابت هم درست نیست.
ببینید اگه کتاب ساختمان پوران رو دارید صفحه ۱۱ رو یه نگاه بندازید میبینید که تابع رو با عدد ثابت مقایسه کرده و هیچ مشکلی هم نداره
خود استاد یوسفی هم توی جزوشون عدد ۴ رو با یه تابع مقایسه کردن.
در مورد ضرب بله من لفظا اشتباه گفتم و همون لگاریتم گیری از طرفین منظورمون بوده
(۲۸ مهر ۱۳۹۳ ۱۰:۳۱ ق.ظ)miladcr7 نوشته شده توسط:(28 مهر ۱۳۹۳ ۰۸:۱۹ ق.ظ)MShariati نوشته شده توسط: عذر می‌خوام! من فقط لگاریتم گیری بلدم و اصلاً نمی‌فهمم ضرب کردن در لگاریتم به چه مفهومه!!!
در مورد نزولی بودن هم قبلاً گفتم که کلاً قبولش ندارم، شما مطمئنید که اون عبارت به ازای افزایش n مقادیرش نزولی میشه؟!
بله شما درست میفرمایید.
(۲۸ مهر ۱۳۹۳ ۰۹:۲۸ ق.ظ)Aurora نوشته شده توسط: منظورتون چیه از اینکه در لگاریتم ضرب می کنیم؟ مگه همچین چیزی داریم؟
می تونیم از دو طرف لگاریتم بگیریم نه اینکه در لگاریتم ضرب کنیم.
در مورد نزولی بودن که به نظرم اشتباهه. همچنین مقایسه یک تابع با یک عدد ثابت هم درست نیست.
ببینید اگه کتاب ساختمان پوران رو دارید صفحه ۱۱ رو یه نگاه بندازید میبینید که تابع رو با عدد ثابت مقایسه کرده و هیچ مشکلی هم نداره
خود استاد یوسفی هم توی جزوشون عدد ۴ رو با یه تابع مقایسه کردن.
در مورد ضرب بله من لفظا اشتباه گفتم و همون لگاریتم گیری از طرفین منظورمون بوده
ممنون.
۴ رو با چی مقایسه کرده؟
(۲۶ مهر ۱۳۹۳ ۰۵:۴۰ ب.ظ)MShariati نوشته شده توسط: به گمانم ...
همواره رشد چندجمله‌ای به رشد Polylogarithmic چیره می‌شود و آمیختن Polylogarithmic با چندچمله‌ای توسط ضرب، سبب تغییر توانی در رشد آن چندچمله‌ای نمی‌شود. در بین چندجمله‌ای‌ها هم فارغ از بزرگی ضرایب، آن که با epsilon تفاوت در توانش بزرگتر است، یک کلاس پیچیدگی بالاتر تشکیل می دهد.
بله من لفظا اشتباه گفتم.همون لگاریتم گیری از طرفین درسته
فکر کنم سوال رو اشتباه حل کرده بودم الان که دوباره حل کردم بله فکر کنم حق با شماست
از نظر مربته زمانی
[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]
و واضحه که اون ضریب ثابت ۱۰۰۰۰۰۰۰ در سمت چپ تاثیری در مرتبه زمانی نداره (چون ثابته)
فقط نکته ش اینه که یه چند جمله ای با هر توانی (هر چند خیییییییییییییلی کوچک) همواره مرتبه ی بیشتری نسبت به یک لگاریتم با هر توانی ( هر چند خییییییییلی بزرگ) دارد.