کلا این عبارت اول که نوشته اید عبارت صحیحی نیست که بخواهید برای آن استدلال بیاورید یا آن را اثبات کنید
اگر [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 یا امگا بیان کرد

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

(۱۹ مهر ۱۳۹۳ ۰۴:۱۷ ق.ظ)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 یا امگا بیان کرد

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

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

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

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

(۱۲ مهر ۱۳۹۳ ۱۰:۲۰ ب.ظ)reza777gh نوشته شده توسط:  

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

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

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

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

(۱۵ مهر ۱۳۹۳ ۰۲:۵۲ ب.ظ)batouei نوشته شده توسط:  

(12 مهر ۱۳۹۳ ۱۰:۲۰ ب.ظ)reza777gh نوشته شده توسط:  

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

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

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

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

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