سلام دوستان
کسی میدونه چرا این عبارت همیشه درست نیست؟؟ (توی کتاب پوران بود ولی نفهمیدمش
)((O(f(n)) - Ω(f(n)) = o(f(n
سلام فرض کن تابع ما این شکلی باشه:
[tex]g(n)=\{^{n\rightarrow n\: is\: even}_{1\rightarrow n\: is\: odd}[/tex]
خب میبینی به ازای [tex]n[/tex] های زوج مقدار تابع [tex]n[/tex] و به ازای [tex]n[/tex] های فرد مقدار تابع [tex]1[/tex] میشه
خب حالا دقت کن که ماکزیمم مقدار تابع [tex]n[/tex] هستش پس:
[tex]g(n)\in O(n)[/tex]
ولی چون مقدار تابع بین [tex]1[/tex] و [tex]n[/tex] متغیره پس داریم:
[tex]g(n)\notin Ω(n)[/tex]
پس حالا داریم که :
[tex]g(n)\in O(n)-Ω(n)[/tex]
خب از طرفی هم معلومه که این تابع عضو [tex]o(n)[/tex] نیستش چون توابعی عضو [tex]o(n)[/tex] هستند که رشدشون کمتر از [tex]o(n)[/tex] باشه ولی رشد این تابع به ازای [tex]n[/tex]های زوج برابر [tex]o(n)[/tex] میشه که قابل قبول نیست
در نهایت:
[tex]O(n)-Ω(n)\ne o(n)[/tex]
(۰۹ مهر ۱۳۹۳ ۱۲:۳۸ ب.ظ)miladcr7 نوشته شده توسط: سلام فرض کن تابع ما این شکلی باشه:
[tex]g(n)=\{^{n\rightarrow n\: is\: even}_{1\rightarrow n\: is\: odd}[/tex]
خب میبینی به ازای [tex]n[/tex] های زوج مقدار تابع [tex]n[/tex] و به ازای [tex]n[/tex] های فرد مقدار تابع [tex]1[/tex] میشه
خب حالا دقت کن که ماکزیمم مقدار تابع [tex]n[/tex] هستش پس:
[tex]g(n)\in O(n)[/tex]
ولی چون مقدار تابع بین [tex]1[/tex] و [tex]n[/tex] متغیره پس داریم:
[tex]g(n)\notin Ω(n)[/tex]
پس حالا داریم که :
[tex]g(n)\in O(n)-Ω(n)[/tex]
خب از طرفی هم معلومه که این تابع عضو [tex]o(n)[/tex] نیستش چون توابعی عضو [tex]o(n)[/tex] هستند که رشدشون کمتر از [tex]o(n)[/tex] باشه ولی رشد این تابع به ازای [tex]n[/tex]های زوج برابر [tex]o(n)[/tex] میشه که قابل قبول نیست
در نهایت:
[tex]O(n)-Ω(n)\ne o(n)[/tex]
ممنون از پاسختون.
