چهارشنبه ۱۰ بهمن ۱۳۸۶
امروز از صبح داشتم برگه‌های یک امتحان طراحی الگوریتم را صحیح می‌کردم یکی از سوال‌ها این بود که ثابت کنید اگر
f(n)\in O(f(n))= O(g(n)) => \exists n1,c1: \forall n>n1, f(n)<> c1*g(n)) (1)
g(n)\in O(g(n))= O(f(n)) => \exists n2,c2: \forall n>n2, g(n)<> c2*f(n)) (2)
(1,2) => \forall n>max(n1,n2) \frac{g(n)}{c2}< f(n)< c1* f(n)
=> f(n) \in \teta(g(n))
\forall h(n) \in \teta (f(n)) => h(n) \in \teta (g(n)) (4)
=>\teta(f(n)) \subset \teta(g(n)).
و به شکل مشابه می‌توان ثابت کرد
و در نتیجه دو مجموعه با هم مساوی هستند.
بعد از تموم شدن تصحیح برگه‌ها دیدم یارو یه برگه گذاشته و توش جواب سوال‌ها را هم برام نوشته. تو جواب خودش اومده بود ثابت کرده بود که
و بعد نتیجه گرفته بود که
یعنی یه قسمته حل را پیچونده!
O(f(n))=O(g(n)) => \teta (f(n))= \teta (g(n))
راه‌حلی که به ذهن من رسید این بود که
f(n)\in O(f(n))= O(g(n)) => \exists n1,c1: \forall n>n1, f(n)<> c1*g(n)) (1)
g(n)\in O(g(n))= O(f(n)) => \exists n2,c2: \forall n>n2, g(n)<> c2*f(n)) (2)
(1,2) => \forall n>max(n1,n2) \frac{g(n)}{c2}< f(n)< c1* f(n)
=> f(n) \in \teta(g(n))
\forall h(n) \in \teta (f(n)) => h(n) \in \teta (g(n)) (4)
=>\teta(f(n)) \subset \teta(g(n)).
و به شکل مشابه می‌توان ثابت کرد
\teta(g(n)) \subset \teta(f(n))
و در نتیجه دو مجموعه با هم مساوی هستند.
بعد از تموم شدن تصحیح برگه‌ها دیدم یارو یه برگه گذاشته و توش جواب سوال‌ها را هم برام نوشته. تو جواب خودش اومده بود ثابت کرده بود که
f(n) \in \teta g(n) , g(n) \in \teta(f(n))
و بعد نتیجه گرفته بود که
teta(f(n))=teta(g(n)).
یعنی یه قسمته حل را پیچونده!
هیچ نظری موجود نیست:
ارسال یک نظر