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

اصلاح سوال"درستی نادرستی" - batouei - 12 مهر ۱۳۹۳ ۰۲:۳۸ ب.ظ

سلام عکس سوالمو attach کردم

RE: اصلاح سوال"درستی نادرستی" - reza777gh - 12 مهر ۱۳۹۳ ۱۰:۲۰ ب.ظ

(۱۲ مهر ۱۳۹۳ ۰۲:۳۸ ب.ظ)batouei نوشته شده توسط:  سلام عکس سوالمو attach کردم

اگر f=n^2
g=n
باشه چی؟!
سوال دوم هم اگه اشتباه نکنم میشه ثابت کرد
n^n/2<n!<n^n
که میشه از مرتبه O ی اون یکی

RE: اصلاح سوال"درستی نادرستی" - batouei - 15 مهر ۱۳۹۳ ۰۲:۵۲ ب.ظ

(۱۲ مهر ۱۳۹۳ ۱۰:۲۰ ب.ظ)reza777gh نوشته شده توسط:  
(12 مهر ۱۳۹۳ ۰۲:۳۸ ب.ظ)batouei نوشته شده توسط:  سلام عکس سوالمو attach کردم

اگر f=n^2
g=n
باشه چی؟!
سوال دوم هم اگه اشتباه نکنم میشه ثابت کرد
n^n/2<n!<n^n
که میشه از مرتبه O ی اون یکی

میگم جوابی که به سوال خودم برای اثبات جمله بالا دادم آیا درسته یا غلطه؟؟

RE: اصلاح سوال"درستی نادرستی" - reza777gh - 15 مهر ۱۳۹۳ ۱۱:۱۰ ب.ظ

(۱۲ مهر ۱۳۹۳ ۰۲:۳۸ ب.ظ)batouei نوشته شده توسط:  سلام عکس سوالمو attach کردم

(۱۵ مهر ۱۳۹۳ ۰۲:۵۲ ب.ظ)batouei نوشته شده توسط:  
(12 مهر ۱۳۹۳ ۱۰:۲۰ ب.ظ)reza777gh نوشته شده توسط:  
(12 مهر ۱۳۹۳ ۰۲:۳۸ ب.ظ)batouei نوشته شده توسط:  سلام عکس سوالمو attach کردم

اگر f=n^2
g=n
باشه چی؟!
سوال دوم هم اگه اشتباه نکنم میشه ثابت کرد
n^n/2<n!<nn
که میشه از مرتبه O ی اون یکی

میگم جوابی که به سوال خودم برای اثبات جمله بالا دادم آیا درسته یا غلطه؟؟

من سعی کردم یه مثال نقض برای استدلال شما بیارم که جمله اول درست باشه ودومی هم درست

RE: اصلاح سوال"درستی نادرستی" - mariy - 18 مهر ۱۳۹۳ ۱۱:۵۴ ب.ظ

جواب سوال اول تون که درسته منم همینجوری تحلیل میکنم.
واما بیاد پیچیدگی هارو باهم مرتب کنیم

RE: اصلاح سوال"درستی نادرستی" - fatemeh69 - 19 مهر ۱۳۹۳ ۰۴:۱۷ ق.ظ

کلا این عبارت اول که نوشته اید عبارت صحیحی نیست که بخواهید برای آن استدلال بیاورید یا آن را اثبات کنید
اگر [tex]f(n)\notin O(g(n))[/tex] آن گاه هر حالتی ممکنه پیش بیاد و دلیلی نمی شه که حتما بگیم [tex]g(n)\in O(f(n))[/tex] نیست یا بگیم عضو امگا هست
حالت های زیادی ممکنه پیش بیاد
مثلا اگر [tex]f(n)=n,\: \: \: g(n)=\log n[/tex] در این صورت [tex]\: g(n)\in O(f(n))[/tex]
یا مثلا اگر f و g به این صورت باشند:

[tex]f=\{n\: \: \: \: \: if\: \: n\: is\: odd,\: \: \: \: \: \: \: \: 2\: \: \: \: \: \: if\: n\: is\: even\}[/tex]
[tex]g=\{2\: \: \: \: \: if\: \: n\: is\: odd,\: \: \: \: \: \: \: \: n\: \: \: \: \: \: if\: n\: is\: even\}[/tex]
در این صورت برای f و g هیچ نسبتی را نمی توان با o یا امگا بیان کرد

پس اساسا عبارت اولتان غلط است پس اثبات و استدلالتان هم برای آن غلط است.

RE: اصلاح سوال"درستی نادرستی" - batouei - 19 مهر ۱۳۹۳ ۱۱:۱۳ ق.ظ

(۱۹ مهر ۱۳۹۳ ۰۴:۱۷ ق.ظ)fatemeh69 نوشته شده توسط:  کلا این عبارت اول که نوشته اید عبارت صحیحی نیست که بخواهید برای آن استدلال بیاورید یا آن را اثبات کنید
اگر [tex]f(n)\notin O(g(n))[/tex] آن گاه هر حالتی ممکنه پیش بیاد و دلیلی نمی شه که حتما بگیم [tex]g(n)\in O(f(n))[/tex] نیست یا بگیم عضو امگا هست
حالت های زیادی ممکنه پیش بیاد
مثلا اگر [tex]f(n)=n,\: \: \: g(n)=\log n[/tex] در این صورت [tex]\: g(n)\in O(f(n))[/tex]
یا مثلا اگر f و g به این صورت باشند:

[tex]f=\{n\: \: \: \: \: if\: \: n\: is\: odd,\: \: \: \: \: \: \: \: 2\: \: \: \: \: \: if\: n\: is\: even\}[/tex]
[tex]g=\{2\: \: \: \: \: if\: \: n\: is\: odd,\: \: \: \: \: \: \: \: n\: \: \: \: \: \: if\: n\: is\: even\}[/tex]
در این صورت برای f و g هیچ نسبتی را نمی توان با o یا امگا بیان کرد

پس اساسا عبارت اولتان غلط است پس اثبات و استدلالتان هم برای آن غلط است.

بله دقیقا. سوال این بوده که این عبارت درسته؟ که جواب نه هست.در واقع چون همیشه درست نیست، جواب منفیه و شما در اون مواردی که عبارت درسته مثال آوردین که مقصود این نیست . در واقع این عبارت رو جایی با یه مثالی نقض کرده بودن که نشون بدن عبارت غلطه و همیشه درست نیست بعد من گفتم در مواردی که این عبارت غلطه پس چه رابطه ای درست هست! در واقع استدلال من برای این مساله بوده