سلام
هنگامی که نمادهای مجانبی را توضیح می دهند به جز تعریفی که در تمام کتاب ها هست یک دید دوم(به نظر آقای وزیرانی) نیز وجود دارد
با این دید که مثلا چه توابعی big-Oآنها [tex]g(n)[/tex] است وقتی بیگ او یک تابع رو می گیریم از مثلا n بعد می توان n به توان ۲ باشد و همینطور به طرف مقادیر بزرگتر اما در این دید تمام کوچکترها تا رسیدن به آن مثلاn در نظر گرفته می شود
مثال: [tex]f(n)=n^{2}[/tex] آنگاه [tex]O(f(n))={n^{2},nlog n, n 5 ,...}[/tex]
این نماد رو در CLRS به شکل[tex]O\infty[/tex] (البته علامت بی نهایت بالای O است) نشان داده
توضیح: O ای که در سوال من در ادامه استفاده می شود Small-o هست
ابتدا یک مثال برای این دید از Small-o
[tex]o(n)={1,. . . ,n^{1-\varepsilon},\frac{n}{log n} }[/tex]
در اینجا تمام توابعی که اوی کوچک آنها n است نوشته شده
سوال: [tex]o(o(n))[/tex]
تمام توابعی که این عبارت مرتبه اجرایی آنهاست را بیابید در دید دوم از این به قبلی ها را می نویسیم
فایل زیر رو هم پیوست کردم، که فصل اول جزوه استاد هست که هم این موضوع رو توضیح داده و هم یه عالمه نمونه سوال حل کرده داره که فکر می کنم به درد دوستان بخوره
جواب به دست اومد، می ذارم دوستان خواستن استفاده کنند
[tex]{1,.....,\frac{n}{log k}}[/tex]
البته لگاریتم k در مبنای n هستش
[attachment=3801]یه فایل دیگه هم پیوست کردم که یه سری فرمولهای مهم به همراه بعضی اثبات هاشون هست، هر کی دانلود کرد یه دعا به جون استاد گلاب پور بکنه