۰
subtitle
ارسال: #۱
تست ۴۴ طراحی الگوریتم آی تی ۹۰
چرا گزاره ضمیمه شده غلط است
زمانی 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 که بر طبق تعریف ای بزرگ حداقل یک 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
با استدلال بالا کزاره درست به نظر می رسد چرا گزاره ضمیمه شده غلط است
خواهشا جواب بدید
۰
۰
ارسال: #۳
تست ۴۴ it90
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 بزرگتر است از( c f(n
دقت کن فقط بزرگتر نه بزرگتر مساوی
حالا داریم توی قسمت نتیجه گیری از رابطه که( g(n)>=cf(n
یعنی (g(n بزرگتر مساوی هست با( cf(n
و در حالی که از قبلی نتیجه گرفتیم شامل مساوی نمیشه
ارسال: #۴
RE: تست ۴۴ it90
(۰۲ بهمن ۱۳۹۰ ۰۱:۳۴ ب.ظ)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 که هست
لطفا اگر تعریف امکا را اشتباه فهمیدم راهنمایی‌ام کنید
۰
ارسال: #۶
RE: تست ۴۴ it90
۰
ارسال: #۷
تست ۴۴ it90
این مورد تناوب که دلیل منطقی هست اما دلیل بزرگ‌مساوی یا کوچکتر مساوی هم فکر میکنم میتونه مطرح باشه... درست نیست؟
۰
ارسال: #۸
تست ۴۴ it90
همینطور که گفتن این تابع روی توابعی‌مثل توابع sinدرست نیست. حرف شما درست هستش و در مواردی برای نمادهای امگا و بیگ او این رابطه صدق میکنه اما لزما با هم ارتباطی ندارن.
حالتی رو تصور کنید که ما مجموعه ای به اسم مثلا A داریم و مجموعه‌ی دیگه ای هست که زیرمجموعه‌ی اونه که میتونه شامل تمام اعضای a بشه و هم میتونه شامل اعضای a بدون اعضای مرزی اون باشه.
دراین صورت من الزاما نمیتونم بگم که این دو مجموعه با هم برابر هستن.
در هر صورت شاید منطق یاد گیری من درمورد این سوالا با شما تفاوت داشته باشه.اما من ازین نمونه‌ها دیگه خیلی حل کردم
بازم اگه خواستید اونو در حالتی که f(n)=|n^2 sin n| و g(n)=n باشه حل کنید
اما برایاین نمونه سوالا دانستن همون منطق >= و <= برای امگا و بیگ او
و > و < برای اسمال او و امگا کوچیک کفایت میکنه و با کمی دقت میشه تشخیص داد
حالتی رو تصور کنید که ما مجموعه ای به اسم مثلا A داریم و مجموعه‌ی دیگه ای هست که زیرمجموعه‌ی اونه که میتونه شامل تمام اعضای a بشه و هم میتونه شامل اعضای a بدون اعضای مرزی اون باشه.
دراین صورت من الزاما نمیتونم بگم که این دو مجموعه با هم برابر هستن.
در هر صورت شاید منطق یاد گیری من درمورد این سوالا با شما تفاوت داشته باشه.اما من ازین نمونه‌ها دیگه خیلی حل کردم
بازم اگه خواستید اونو در حالتی که f(n)=|n^2 sin n| و g(n)=n باشه حل کنید
اما برایاین نمونه سوالا دانستن همون منطق >= و <= برای امگا و بیگ او
و > و < برای اسمال او و امگا کوچیک کفایت میکنه و با کمی دقت میشه تشخیص داد
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close