تقریب توابع در کلاس پیچیدگی لگاریتمی
سلام به همگی من یه سوال دارم اگه کسی می تونه لطفا راهنمایی کنه:
چطوری میشه یه الگوریتمی طراحی کنیم که توابع دلخواه ما را برای مقادیر بزرگ تقریب کنه و الگوریتم در مرتبه زمانی لگاریتمی باشه؟ Logspace
یعنی فرض کنید میخواهیم تابع ((f(n)=Log(Bessel I0(n را برای مقادیر ...,n= 2^2 ,2^4 ,2^8 ,2^16
برآورد کنیم و زمان حل مساله را هم اندازه میگیریم این زمان برای nهای داده شده باید تناسب هندسی داشته باشه یعنی زمان حل مساله در هر n نسبت به n قبلی در یک عدد ثابت ضرب شده باشه.من اینکار رو برای هر تابعی که خواستم با برنامه Mathematica انجام دادم ولی نمیدونم چطوری برنامه اینکارو میکنه؟ جالب اینجاست که روشهای مرسوم تقریب توابع مثل سریهای تیلور و فوریه و چبیشف و کسرهای پده (pade) و کسرهای متوالی هیچکدوم در زمان لگاریتمی نمیتونن تقریب کنن من امتحان کردم.
اگه کسی چنین الگوریتمی سراغ داره لطفا بگه یا لینک کنه
ممنون
کیوان
