یک مثال نقص برای رد این رابطه بیاورید
[tex]f(n) \epsilon O(g(n)) \Rightarrow 2^{f(n)}\epsilon O (2^{g(n)} )[/tex]
(۰۶ خرداد ۱۳۹۲ ۱۰:۴۰ ق.ظ)atharrashno نوشته شده توسط: یک مثال نقص برای رد این رابطه بیاورید
[tex]f(n) \epsilon O(g(n)) \Rightarrow 2^{f(n)}\epsilon O (2^{g(n)} )[/tex]
[tex]F(n) = 2n \, \, \, , \, \, \, G(n) = n[/tex]
درسته
و اگر او بزرگ به او کوچیک تبدیل بشه ان وقت مثال نقضش چی میشه؟
با تبدیل بیگ O به لیتل O، مثال نقضی رو نمی توان زد و رابطه درست خواهد بود.
این سوال رو قبلا هم بررسی کردیم، می تونید به این تاپیک مراجعه کنید.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
سلام.
من درست دلیل نادرستی این رابطه رو متوجه نشدم!!
این مثال نقض که آوردین میشه ثابت کرد که [tex]2^{2n}=O \left ( 2^{n} \right )[/tex]
اگر مثلا c=10 , n=2 باشه. درست نمیگم؟
قبول هم دارم که [tex]2^{2n}[/tex] رشدش از [tex]2^{n} \right[/tex] بیشتره!! اما مگه برا اثبات بیگ او اگر حداقل یه c , n رو داشته باشیم ، کافیه!!! درسته؟
مرسی
(۱۷ مهر ۱۳۹۲ ۰۹:۲۷ ق.ظ)zeinab نوشته شده توسط: مگه برا اثبات بیگ او اگر حداقل یه c , n رو داشته باشیم ، کافیه!!! درسته؟یک بار دیگه تعریف ریاضی نماد بیگ اُ رو مرور کنید. قضیه فقط پیدا کردن یک [tex]n_0[/tex] و c نیست. یه شرط مهم وجود داره که میگه برای تمام nهای بزرگتر مساوی [tex]n_0[/tex] باید داشته باشیم [tex]f(n)\leq c\cdot g(n)[/tex]
(۱۷ مهر ۱۳۹۲ ۰۳:۴۱ ب.ظ)mfXpert نوشته شده توسط:(17 مهر ۱۳۹۲ ۰۹:۲۷ ق.ظ)zeinab نوشته شده توسط: مگه برا اثبات بیگ او اگر حداقل یه c , n رو داشته باشیم ، کافیه!!! درسته؟یک بار دیگه تعریف ریاضی نماد بیگ اُ رو مرور کنید. قضیه فقط پیدا کردن یک [tex]n_0[/tex] و c نیست. یه شرط مهم وجود داره که میگه برای تمام nهای بزرگتر مساوی [tex]n_0[/tex] باید داشته باشیم [tex]f(n)\leq c\cdot g(n)[/tex]
تشکر. متوجه شدم!!
(۰۶ خرداد ۱۳۹۲ ۰۵:۲۲ ب.ظ)azad_ahmadi نوشته شده توسط: با تبدیل بیگ O به لیتل O، مثال نقضی رو نمی توان زد و رابطه درست خواهد بود.برای اوی کوچیک هم غلطه.
این سوال رو قبلا هم بررسی کردیم، می تونید به این تاپیک مراجعه کنید.
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.