تالار گفتمان مانشت
سوال در مورد مرتبه زمانی - نسخه‌ی قابل چاپ

سوال در مورد مرتبه زمانی - mj.net - 15 بهمن ۱۳۹۲ ۰۶:۴۶ ب.ظ

دو تا سوال هست که هر دو مثل همه و به نظر من جوابشون باید nlognبشه
بر اساس قضیه مستر اگه درجه ی f(n) از n به توان لگاریتم a در مبنای b بیشتر باشه تی ان برابر با تتای f(n) میشه
اما توی این دو مسأله برابر f(n)*logn شده. یعنی در حالتی که طبق مستر f(n) و n به توان لگاریتم هم درجه باشند
ممنون میشم کسی راهنمایی کنه
خیلی مهمه این سبک سوالات

[attachment=15230]
[attachment=15229]
[attachment=15231]

RE: سوال در مورد مرتبه زمانی - e.shrm - 16 بهمن ۱۳۹۲ ۰۸:۴۲ ق.ظ

(۱۵ بهمن ۱۳۹۲ ۰۶:۴۶ ب.ظ)mj.net نوشته شده توسط:  دو تا سوال هست که هر دو مثل همه و به نظر من جوابشون باید nlognبشه
بر اساس قضیه مستر اگه درجه ی f(n) از n به توان لگاریتم a در مبنای b بیشتر باشه تی ان برابر با تتای f(n) میشه
اما توی این دو مسأله برابر f(n)*logn شده. یعنی در حالتی که طبق مستر f(n) و n به توان لگاریتم هم درجه باشند
ممنون میشم کسی راهنمایی کنه
خیلی مهمه این سبک سوالات

مجبور شدم لپ تاپو بچرخونم سوالتونو بخونم !! چرا برعکسه! Smile

به نظرم اولی میشه nlogn (لگاریتم به نمای دو).

----------------------
کلا هر وقت اختلاف بین فرمول مستر و fn تو یه log باشه ، میشه همون fn ولی به توان log یه واحد اضافه میشه.
----------------------
اصلاح میکنم . من ندیدم نوشته ۴Tn . دومی هم میشه به نظرم nlogn (لگاریتم به نمای دو).

RE: سوال در مورد مرتبه زمانی - masoud67 - 16 بهمن ۱۳۹۲ ۰۹:۱۷ ق.ظ

(۱۵ بهمن ۱۳۹۲ ۰۶:۴۶ ب.ظ)mj.net نوشته شده توسط:  دو تا سوال هست که هر دو مثل همه و به نظر من جوابشون باید nlognبشه
بر اساس قضیه مستر اگه درجه ی f(n) از n به توان لگاریتم a در مبنای b بیشتر باشه تی ان برابر با تتای f(n) میشه
اما توی این دو مسأله برابر f(n)*logn شده. یعنی در حالتی که طبق مستر f(n) و n به توان لگاریتم هم درجه باشند
ممنون میشم کسی راهنمایی کنه
خیلی مهمه این سبک سوالات
سوال اول که مشخصه [tex]n(logn)^2[/tex] میشه. چون قسمت اول رابطه n میشه و قسمت دوم !logn برابر هست که با nlogn یکسانه و چون در یک logn با هم تفاوت دارند پس باید یه log به عبارت نهایی اضافه کرد و میشه [tex]n(logn)^2[/tex]

-----------------------------------------------
بعد از دیدن عکس عمودی به صورت افقی ، متوجه شدیم که رابطه سوال چیز دیگری است . و مورد دوم هم مثل مورد اول میباشد

RE: سوال در مورد مرتبه زمانی - e.shrm - 16 بهمن ۱۳۹۲ ۰۹:۲۶ ق.ظ

(۱۶ بهمن ۱۳۹۲ ۰۹:۱۷ ق.ظ)masoud67 نوشته شده توسط:  
(15 بهمن ۱۳۹۲ ۰۶:۴۶ ب.ظ)mj.net نوشته شده توسط:  دو تا سوال هست که هر دو مثل همه و به نظر من جوابشون باید nlognبشه
بر اساس قضیه مستر اگه درجه ی f(n) از n به توان لگاریتم a در مبنای b بیشتر باشه تی ان برابر با تتای f(n) میشه
اما توی این دو مسأله برابر f(n)*logn شده. یعنی در حالتی که طبق مستر f(n) و n به توان لگاریتم هم درجه باشند
ممنون میشم کسی راهنمایی کنه
خیلی مهمه این سبک سوالات
سوال اول که مشخصه [tex]n(logn)^2[/tex] میشه. چون قسمت اول رابطه n میشه و قسمت دوم !logn برابر هست که با nlogn یکسانه و چون در یک logn با هم تفاوت دارند پس باید یه log به عبارت نهایی اضافه کرد و میشه [tex]n(logn)^2[/tex]

در مورد دومی که استفاده از مستر جایز نیست و فکر کنم مرتبه اش بشه [tex]O(n)[/tex] چون داره به صورت خطی در هر مرحله مقدار n یه دونه کم میشه
شرطی که برای fn تو مستر وجود داره چیه؟

RE: سوال در مورد مرتبه زمانی - fulgent - 16 بهمن ۱۳۹۲ ۰۹:۳۷ ق.ظ

جواب هر دو میشه (T(n) = O(n logn^2

RE: سوال در مورد مرتبه زمانی - masoud67 - 16 بهمن ۱۳۹۲ ۰۹:۴۰ ق.ظ

(۱۶ بهمن ۱۳۹۲ ۰۹:۲۶ ق.ظ)e.shrm نوشته شده توسط:  شرطی که برای fn تو مستر وجود داره چیه؟
این Tex باز گیج شد و نشد فرمول بنویسم ولی خوش یمن بود چون رفتم از تو یه فایل عکس بردارم و بذارم ، زیرش دقیقا همین مثال رو گذاشته بود


اما اگه در مورد دومی منظورتونه که کلا با اصل مستر فرق داره و از اون روش حل نمیشه

RE: سوال در مورد مرتبه زمانی - e.shrm - 16 بهمن ۱۳۹۲ ۰۹:۵۵ ق.ظ

(۱۶ بهمن ۱۳۹۲ ۰۹:۴۰ ق.ظ)masoud67 نوشته شده توسط:  
(16 بهمن ۱۳۹۲ ۰۹:۲۶ ق.ظ)e.shrm نوشته شده توسط:  شرطی که برای fn تو مستر وجود داره چیه؟
این Tex باز گیج شد و نشد فرمول بنویسم ولی خوش یمن بود چون رفتم از تو یه فایل عکس بردارم و بذارم ، زیرش دقیقا همین مثال رو گذاشته بود


اما اگه در مورد دومی منظورتونه که کلا با اصل مستر فرق داره و از اون روش حل نمیشه
من قبل از شما یه جوابی دادم اون بالا!
اولی که بدیهیه.
برای دومی که گفتید مستر نمیشه.
چرا نمیشه گفت بخش fn به طور کلی از مرتبه nlogn هست (حد بالا) و بعد از مستر استفاده کرد؟

RE: سوال در مورد مرتبه زمانی - masoud67 - 16 بهمن ۱۳۹۲ ۰۹:۵۷ ق.ظ

(۱۵ بهمن ۱۳۹۲ ۰۶:۴۶ ب.ظ)mj.net نوشته شده توسط:  دو تا سوال هست که هر دو مثل همه و به نظر من جوابشون باید nlognبشه
بر اساس قضیه مستر اگه درجه ی f(n) از n به توان لگاریتم a در مبنای b بیشتر باشه تی ان برابر با تتای f(n) میشه
اما توی این دو مسأله برابر f(n)*logn شده. یعنی در حالتی که طبق مستر f(n) و n به توان لگاریتم هم درجه باشند
ممنون میشم کسی راهنمایی کنه
خیلی مهمه این سبک سوالات
تو عکس سومی دقیقا رابطه چیه ؟ اگه مرتبه را بخواد که این چیزی که شما نوشتی داره به صورت نمایی زیاد میشه
اگر زمان اجراشو میخواسته (که من اشتباها فرض را بر این گذاشتم) میشه مرتبه n

(۱۶ بهمن ۱۳۹۲ ۰۹:۵۵ ق.ظ)e.shrm نوشته شده توسط:  
(16 بهمن ۱۳۹۲ ۰۹:۴۰ ق.ظ)masoud67 نوشته شده توسط:  
(16 بهمن ۱۳۹۲ ۰۹:۲۶ ق.ظ)e.shrm نوشته شده توسط:  شرطی که برای fn تو مستر وجود داره چیه؟
این Tex باز گیج شد و نشد فرمول بنویسم ولی خوش یمن بود چون رفتم از تو یه فایل عکس بردارم و بذارم ، زیرش دقیقا همین مثال رو گذاشته بود


اما اگه در مورد دومی منظورتونه که کلا با اصل مستر فرق داره و از اون روش حل نمیشه
من قبل از شما یه جوابی دادم اون بالا!
اولی که بدیهیه.
برای دومی که گفتید مستر نمیشه.
چرا نمیشه گفت بخش fn به طور کلی از مرتبه nlogn هست (حد بالا) و بعد از مستر استفاده کرد؟
آخه تو عکس سومی ایشون نوشته T(n)= T(4(n-1)) + n/16*Logn + n/2
مستر اصلا چنین رابطه ای را حل نمیکنه. اینو نمیدونم از چه رابطه ای باید حل کرد چون اگر مقدار گذاری کنید ، تابع فقط داره زیاد میشه و رشد نمایی داره
اونی که گفتم میشه n منظورم زمان اجراش بود نه مرتبه الگوریتم.
اگه چیزی که شما میگید مستر این رابطه را چی میده
T(n) = T(n-1) + n
مرتبه الگوریتم این میشه n^2 . ولی با چیزی که شما گفتید مرتبه اش باید بشه nlogn

RE: سوال در مورد مرتبه زمانی - e.shrm - 16 بهمن ۱۳۹۲ ۱۰:۰۹ ق.ظ

(۱۶ بهمن ۱۳۹۲ ۰۹:۵۷ ق.ظ)masoud67 نوشته شده توسط:  
(16 بهمن ۱۳۹۲ ۰۹:۵۵ ق.ظ)e.shrm نوشته شده توسط:  
(16 بهمن ۱۳۹۲ ۰۹:۴۰ ق.ظ)masoud67 نوشته شده توسط:  
(16 بهمن ۱۳۹۲ ۰۹:۲۶ ق.ظ)e.shrm نوشته شده توسط:  شرطی که برای fn تو مستر وجود داره چیه؟
این Tex باز گیج شد و نشد فرمول بنویسم ولی خوش یمن بود چون رفتم از تو یه فایل عکس بردارم و بذارم ، زیرش دقیقا همین مثال رو گذاشته بود


اما اگه در مورد دومی منظورتونه که کلا با اصل مستر فرق داره و از اون روش حل نمیشه
من قبل از شما یه جوابی دادم اون بالا!
اولی که بدیهیه.
برای دومی که گفتید مستر نمیشه.
چرا نمیشه گفت بخش fn به طور کلی از مرتبه nlogn هست (حد بالا) و بعد از مستر استفاده کرد؟
آخه تو عکس سومی ایشون نوشته T(n)= T(4(n-1)) + n/16*Logn + n/2
مستر اصلا چنین رابطه ای را حل نمیکنه. اینو نمیدونم از چه رابطه ای باید حل کرد چون اگر مقدار گذاری کنید ، تابع فقط داره زیاد میشه و رشد نمایی داره
اونی که گفتم میشه n منظورم زمان اجراش بود نه مرتبه الگوریتم.
اگه چیزی که شما میگید مستر این رابطه را چی میده
T(n) = T(n-1) + n
مرتبه الگوریتم این میشه n^2 . ولی با چیزی که شما گفتید مرتبه اش باید بشه nlogn
--------------------
اونی که شما جواب دادید راه حل خودشونه! نه صورت مساله. صورت مساله یک کم پایین تره!

RE: سوال در مورد مرتبه زمانی - masoud67 - 16 بهمن ۱۳۹۲ ۱۰:۱۴ ق.ظ

(۱۶ بهمن ۱۳۹۲ ۱۰:۰۹ ق.ظ)e.shrm نوشته شده توسط:  اونی که شما جواب دادید راه حل خودشونه! نه صورت مساله. صورت مساله یک کم پایین تره!
Tongue
هیمنه دیگه. عکس کج میذارن ، ما موبایلمون اسکرول نمیخوره و شروع میکنیم چرت و پرت گفتن
دومی هم مثل اولی میشه. حق با شماست

RE: سوال در مورد مرتبه زمانی - maryam.raz - 16 بهمن ۱۳۹۲ ۰۲:۴۵ ب.ظ

ظاهرا پست های دیشب همه پاک شده چون من دیشب جواب دادم
هر دو سوال از این قضیه استفاده کردن
تبصره در قضیه اصلی:
اگه رابطه بازگشتی بصورت زیر باشه :
[tex]T(n)=aT(\frac{n}{b}) n^{log_{b}^{a}}*logn^{d}[/tex]
اونوقت حاصل میشه :
[tex]n^{log_{b}^{a}}*log^{d 1}[/tex]

همون fn فقط به توان لگاریتمش(d) یه واحد اضافه میشه

RE: سوال در مورد مرتبه زمانی - mj.net - 16 بهمن ۱۳۹۲ ۱۱:۵۷ ب.ظ

سلام به همگی
من نمیدونم چرا عکسا کج شدن :دی
مریم.راز دیشب جواب داد و منم جواب دادم. پاک شده
ممنون از همگی
این رابطه رو توی مستر من بلد نبودم. مستر دیگه چی داره که من بلد نیستم ؟ Confused
فقط همون سه حالت کمتر مساوی بیشتر و میدونم ازش
عکس سوم هم همون سوال پارسه هست تو ۱۰۰ دوم. وقتی تبدیلش کرده به شکل مستر در میاد.
فقط یه سوال دیگه که اگه [tex]aT\left ( n/b - 1 \right ) f\left ( n \right )[/tex] باشه دیگه مستر نیست ؟

(۱۶ بهمن ۱۳۹۲ ۰۲:۴۵ ب.ظ)maryam.raz نوشته شده توسط:  اگه رابطه بازگشتی بصورت زیر باشه :
[tex]T(n)=aT(\frac{n}{b}) n^{log_{a}^{b}}*logn^{d}[/tex]
اونوقت حاصل میشه :
[tex]n^{log_{a}^{b}}*log^{d 1}[/tex]

ممنون ... فقط توی لگاریتم جای a و b عوض شده. اشتباه لپیه
دیشب این و سوال کرده بودم که دوستان زحمت کشیدن عکسش رو گذاشتن

(۱۶ بهمن ۱۳۹۲ ۰۸:۴۲ ق.ظ)e.shrm نوشته شده توسط:  مجبور شدم لپ تاپو بچرخونم سوالتونو بخونم !! چرا برعکسه! Smile

نمیدونم چرا برعکس شده. فقط شما چرا لپتاپ و چرخوندی ؟؟؟ خوب عکس و سیو میکردی Big Grin
جا داره یادی از پت و مت عزیز بکنیم
بازم ممنون Heart

RE: سوال در مورد مرتبه زمانی - maryam.raz - 17 بهمن ۱۳۹۲ ۰۱:۲۷ ق.ظ

(۱۶ بهمن ۱۳۹۲ ۱۱:۵۷ ب.ظ)mj.net نوشته شده توسط:  ممنون ... فقط توی لگاریتم جای a و b عوض شده. اشتباه لپیه
دیشب این و سوال کرده بودم که دوستان زحمت کشیدن عکسش رو گذاشتن

نمیدونم چرا برعکس شده. فقط شما چرا لپتاپ و چرخوندی ؟؟؟ خوب عکس و سیو میکردی Big Grin
جا داره یادی از پت و مت عزیز بکنیم
بازم ممنون Heart
من که رابطه دیگه ای بلد نیستم از مستر
درستش کردم فرمولو. از بس این فرمول نویسی قات داشت هزار بار نوشتم دیگه خودمم قاتی کردمBig Grin