۱/ اگر f(n)= 2n^2+n و g(n)=O(n^2 چه چیزی در جمله زیر نادرست است؟
f(n)=O(n^2)+O(n) طوریکه
f(n)-g(n)=O(n^2)+O(n)-O(n^2
بنابراین f(n)-g(n)=O(n)
(۱۱ مهر ۱۳۹۱ ۰۲:۰۲ ب.ظ)f_a نوشته شده توسط: ۱/ اگر f(n)= 2n^2+n و g(n)=O(n^2 چه چیزی در جمله زیر نادرست است؟
f(n)=O(n^2)+O(n) طوریکه
f(n)-g(n)=O(n^2)+O(n)-O(n^2
بنابراین f(n)-g(n)=O(n)
این سوال با اینکه واسه فصل اول نظریه است اما بیشتر به الگوریتمها بر میگرده!
منم موقع خوندن این سوال کمی گیج شدم اما وقتی CLRS خوندم با این توجیه برای خودم جا انداختمش! نمیدونم چقدر توجیهم درسته
ما برای یک "چند جمله ای" میتونیم یک اوی بزرگ داشته باشیم یعنی برای [tex]f(n)= O(n^{2})[/tex]
در تابع بعدی فقط مقدار اوی بزرگ رو به ما داده!
نمیشه یه تابع که بطور کامل نوشته شده رو با تابعی که فقط مقدار حدی اون داده چنین مقایسه ای کرد!
o(n) - o(n) = o(n . ببینید اینا کران بالا واسه مقادیر اصلی هستن.با یه مثال ساده می تونی بهش برسی به نظر من. ۲n از o(n) هست و n هم از o(n) . حالا ۲n -n هم o(n) هست. امیدوارم تونسته باشم کمکت کنم.
خب مشکلش اینه تو جواب دو تا O(N^2) رو با هم ساده کرده و به اون جواب رسیده در حالی که همچین کاری نمیتونسته بکنه
