چرا گزاره ضمیمه شده غلط است
زمانی g(n) = o(f(n که بر طبق تعریف ای بزرگ حداقل یک c باشد که g(n)<= c f(n پس جال که
g(n) <> o(f(n یعتی به ازای همه cها g(n)> c f(n
بر ظبق تعریفی که از g(n از مرتبه امکای f(n داریم به ازای حداقل یک c
g(n)= c f(n یا g(n)> c f(n باشد g صورت سوال مطایق با شرایظ ذکر شذه در مقدم گزاره شرطی و توضیحات ذکر شده در بالا به ازای همه cها g(n)> c f(n است پس یعنی حداقل یک c با شرایط مورد نظر امکا وجود دارد یعنی g(n از مرتبه امکای f(n
با استدلال بالا کزاره درست به نظر می رسد چرا گزاره ضمیمه شده غلط است
خواهشا جواب بدید
g(n)=O f(n
یعنی (g(n کوچیکتر مساوی هست با (c f(n
حالا وقتی این میشه نامساوی یعنی (g(n بزرگتر است از( c f(n
دقت کن فقط بزرگتر نه بزرگتر مساوی
حالا داریم توی قسمت نتیجه گیری از رابطه که( g(n)>=cf(n
یعنی (g(n بزرگتر مساوی هست با( cf(n
و در حالی که از قبلی نتیجه گرفتیم شامل مساوی نمیشه
(۰۲ بهمن ۱۳۹۰ ۰۱:۳۴ ب.ظ)zzsnowdrop نوشته شده توسط: g(n)=O f(nبا تشکر از جوابتان
یعنی (g(n کوچیکتر مساوی هست با (c f(n
حالا وقتی این میشه نامساوی یعنی (g(n بزرگتر است از( c f(n
دقت کن فقط بزرگتر نه بزرگتر مساوی
حالا داریم توی قسمت نتیجه گیری از رابطه که( g(n)>=cf(n
یعنی (g(n بزرگتر مساوی هست با( cf(n
و در حالی که از قبلی نتیجه گرفتیم شامل مساوی نمیشه
قبول دارم که (g(n بزرگتر است از( c f(n نه بزرگتر مساوی
ولی در تعریف امگا داریم که اگر g(n از مرتبه امگای f(n باشد انگاه( g(n)=cf(n
یا
( g(n)>cf(n
درست است که g با شرایط ذکر شده در سوال مساوی cf(n نیست ولی حداقل به ازای یک c
( g(n)>cf(n که هست
لطفا اگر تعریف امکا را اشتباه فهمیدم راهنمایی‌ام کنید
ممکنه g نموداری نوسانی داشته باشه . مثل سینوس یا کسینوس.
(۰۲ بهمن ۱۳۹۰ ۱۰:۵۴ ب.ظ)si.mozhgan نوشته شده توسط: ممکنه g نموداری نوسانی داشته باشه . مثل سینوس یا کسینوس.
ممنون از جوابتان ولی متوجه نشدم حرفی که زدید با حرفهایی که من زدم جه ارتباطی داره
(۰۳ بهمن ۱۳۹۰ ۱۲:۱۴ ق.ظ)rad.bahar نوشته شده توسط:(02 بهمن ۱۳۹۰ ۱۰:۵۴ ب.ظ)si.mozhgan نوشته شده توسط: ممکنه g نموداری نوسانی داشته باشه . مثل سینوس یا کسینوس.
ممنون از جوابتان ولی متوجه نشدم حرفی که زدید با حرفهایی که من زدم جه ارتباطی داره
منظور تناوب است. نمودار sinx را در نظر بگیرد. فرض کنید رفتار الگوریتمی سینوسی باشد. نمودار متناوب است. حالا اگر تابع g(x) را یک تابع ثابت در نظر بگیریم می شود یک مثال نقص!
به شکل ضمیمه توجه کنید
این دو تابع هیچ کرانی برای هم نیستند به ازای هیچ c
این مورد تناوب که دلیل منطقی هست اما دلیل بزرگ‌مساوی یا کوچکتر مساوی هم فکر میکنم میتونه مطرح باشه... درست نیست؟
همینطور که گفتن این تابع روی توابعی‌مثل توابع sinدرست نیست. حرف شما درست هستش و در مواردی برای نمادهای امگا و بیگ او این رابطه صدق میکنه اما لزما با هم ارتباطی ندارن.
حالتی رو تصور کنید که ما مجموعه ای به اسم مثلا A داریم و مجموعه‌ی دیگه ای هست که زیرمجموعه‌ی اونه که میتونه شامل تمام اعضای a بشه و هم میتونه شامل اعضای a بدون اعضای مرزی اون باشه.
دراین صورت من الزاما نمیتونم بگم که این دو مجموعه با هم برابر هستن.
در هر صورت شاید منطق یاد گیری من درمورد این سوالا با شما تفاوت داشته باشه.اما من ازین نمونه‌ها دیگه خیلی حل کردم
بازم اگه خواستید اونو در حالتی که f(n)=|n^2 sin n| و g(n)=n باشه حل کنید
اما برایاین نمونه سوالا دانستن همون منطق >= و <= برای امگا و بیگ او
و > و < برای اسمال او و امگا کوچیک کفایت میکنه و با کمی دقت میشه تشخیص داد