صفحهها: ۱ ۲
با سلام
جواب این سوال چی میشه
[tex]if f= O(g) then 2^{f} \epsilon O (2^{g})[/tex]
tex]
ایا درست هست نتیجه یا نه و چرا
ممنون میشم پاسخ بدید
با سپاس
اشتباهه. چون مثلا f = 2n و g=n ، هرچند هردو از مرتبه Oبزرگ n هستند اما بعد از then این شرط برقرار نیست و f از g بزرگتر میشه.
(۱۱ مهر ۱۳۹۱ ۱۱:۴۸ ب.ظ)azad_ahmadi نوشته شده توسط: اشتباهه. چون مثلا f = 2n و g=n ، هرچند هردو از مرتبه Oبزرگ n هستند اما بعد از then این شرط برقرار نیست و f از g بزرگتر میشه.توابع f و g که مثال زدید مناسب نیستند چون ۲n از مرتبه لیتل اُوی n نیست
(۱۲ مهر ۱۳۹۱ ۰۲:۱۹ ب.ظ)mfXpert نوشته شده توسط:(11 مهر ۱۳۹۱ ۱۱:۴۸ ب.ظ)azad_ahmadi نوشته شده توسط: اشتباهه. چون مثلا f = 2n و g=n ، هرچند هردو از مرتبه Oبزرگ n هستند اما بعد از then این شرط برقرار نیست و f از g بزرگتر میشه.توابع f و g که مثال زدید مناسب نیستند چون ۲n از مرتبه لیتل اُوی n نیست
سلام. قبل اینکه جواب رو بنویسم، نوشته بودم "آیا اون o، اوی بزرگه یا اوی کوچیک؟" اما پاکش کردم و حدسمو گذاشتم بر اینکه اوی بزرگ باشه. شما درست می گین. ممنون.
---------------------------------------
درضمن اون عکس پروفایلت رو من تا چند ماه فکر می کردم عکس خروسه
اما امروز متوجه شدم که خروس نیست موفق باشی .
(۱۰ مهر ۱۳۹۱ ۰۲:۳۵ ب.ظ)*angle* نوشته شده توسط: با سلام
جواب این سوال چی میشه
[tex]if f= o(g) then 2^{f} \epsilon (2^{g})[/tex]
ایا درست هست نتیجه یا نه و چرا
ممنون میشم پاسخ بدید
با سپاس
احساس میکنمو احتمالا سوال مشکل داره که احتمالا مشکل تایپیه!!!
بعد از then رو دقت کنین,و احتمالا بعد از علامت عضو رو دقت بفرمایین.
اگه من اشتبا میکنم لطفا بگین.
سوال مشکل نداره و کاملا درسته.
جوابش هم میشه "اشتباه است".
(۱۲ مهر ۱۳۹۱ ۱۱:۲۲ ب.ظ)azad_ahmadi نوشته شده توسط: سوال مشکل نداره و کاملا درسته.
جوابش هم میشه "اشتباه است".
مگه نباید بعد از علامت عضویت یکی از علامت های تتا و یا امگا و یا اُ بیاد؟
اشتباه تایپی رو باید حدس زد
قبلش نوشته اگه f عضو اوی کوچیک g باشه، پس احتمالا منظورش بعد از then همون اوی کوچیک هست.
اشتباه تایپی به وفور یافت میشه دوست عزیز.
(۱۲ مهر ۱۳۹۱ ۱۱:۲۹ ب.ظ)azad_ahmadi نوشته شده توسط: اشتباه تایپی رو باید حدس زد
قبلش نوشته اگه f عضو اوی کوچیک g باشه، پس احتمالا منظورش بعد از then همون اوی کوچیک هست.
اشتباه تایپی به وفور یافت میشه دوست عزیز. نگران نباش. موفق باش.
یعنی شما میگید این اشتباهه؟
[tex]if n=o(n^{2}) then 2^{n}\epsilon o(2^{n^{2}})[/tex]
ببینید من تو پست شماره ۲، فرض رو بر این گذاشتم که اون او، اوی بزرگ هست. اگه اینطور باشه که جواب اشتباهه و مثال هم زدم. اما اگه اوی کوچیک باشه، درست خواهد بود.
به نظز من اگه هر دو o کوچک باشند رابطه درسته چون در قسمت اول ثابت میشه که درجه f از G کمتره یعنی حالاتی که میشه مثال زد برای این دو مثل: f=n ,g=n^2 و در قسمت دومم با توجه به این مثال درسته
مرسی از پاسخ من بد تایپ کردم عذرخواهی می کنم منظورم ا بزرگ بود که در اینصورت طبق نظر شما این رابطه اشتباه می شوذ؟
(۱۶ مهر ۱۳۹۱ ۰۱:۳۳ ق.ظ)*angle* نوشته شده توسط: مرسی از پاسخ من بد تایپ کردم عذرخواهی می کنم منظورم ا بزرگ بود که در اینصورت طبق نظر شما این رابطه اشتباه می شوذ؟
سلام. بله جواب سوال اشتباه است. موفق باشی.
این معادله بازگشتی رو که مربو میشه به مرتب سازی ادغامی چه طوری باید اثباتش کنیم ؟
t(n)= 2t(n/2)+(n-1
(راهنماییش هم اینه:
n=2^k فرض کنیم.و بعد از یه سری محاسبات به این برسیم:
t(n)=O(nlog
)
کـــــــــــــــــــــــــــمکـــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ!!!!!!!!!!!!!!!!!!!!!!!!
(۲۹ مهر ۱۳۹۱ ۰۴:۱۶ ب.ظ)roofia نوشته شده توسط: این معادله بازگشتی رو که مربو میشه به مرتب سازی ادغامی چه طوری باید اثباتش کنیم ؟
t(n)= 2t(n/2)+(n-1
(راهنماییش هم اینه:
n=2^k فرض کنیم.و بعد از یه سری محاسبات به این برسیم:
t(n)=O(nlog
)
کـــــــــــــــــــــــــــمکـــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــــ!!!!!!!!!!!!!!!!!!!!!!!!
مرتب سازی ادغامی هر بار مجموعه داده شده رو تقریبا نصف می کنه، تا بجایی برسه که ادامه نصف کردن امکان پذیر نباشه.
پس چون هر بار مجموعه نصف میشه، به دو مجموعه تقسیم بندی میشه. (یعنی n ، به دو مجموعه n/2 تبدیل میشه).
پس تا اینجا ۲T(n/2 مشخص شد. اون n-1 که نوشتین زمان لازم برای مقایسه عناصر بوده که از مرتبه تتای n است.
حالا رابطه بازگشتی که شما نوشتین رو میشه راحت با قضیه اصلی بدست آورد. که جواب برابر تتای nlogn خواهد بود.