advertise laitec sharif univercity
دانلود پروژه مهندسی نرم افزار ، نمایندگی ایران خودرو

دانلود پروژه مهندسی نرم افزار ، نمایندگی ایران خودرو

10000 تومان
دانلود آپلود سنتر پیشرفته با PHP و Ajax

دانلود آپلود سنتر پیشرفته با PHP و Ajax

10000 تومان
دانلود سورس پروژه فروشگاه کیف با asp.net و sql express

دانلود سورس پروژه فروشگاه کیف با asp.net و sql express

10000 تومان
سورس پروژه پایانی آزمون گیری با زبان سی شارپ و SQL

سورس پروژه پایانی آزمون گیری با زبان سی شارپ و SQL

18000 تومان
سیستم اتوماسیون دهیاری ، پروژه مهندسی نرم افزار

سیستم اتوماسیون دهیاری ، پروژه مهندسی نرم افزار

10000 تومان

آنالیز استهلاکی الگوریتم ها

در Amortized Analysis آنالیز استهلاکی برای تخمین زمان اجرای الگوریتم و پیچیدگی زمانی آن، n عمل انجام میشود و هزینه زمانی آن روی n عمل سرشکن میشود. در واقع ممکن است عملیات انجام شده هزینه های مختلفی داشته باشند و برخی هزینه زیادی داشته باشند ولی هزینه متوسط هر عمل کوچک باشد.
آنالیز استهلاکی الگوریتم ها

آنالیز استهلاکی الگوریتم ها

در Amortized Analysis آنالیز استهلاکی برای تخمین زمان اجرای الگوریتم و پیچیدگی زمانی آن، n عمل انجام میشود و هزینه زمانی آن روی n عمل سرشکن میشود. در واقع ممکن است عملیات انجام شده هزینه های مختلفی داشته باشند و برخی هزینه زیادی داشته باشند ولی هزینه متوسط هر عمل کوچک باشد. لازم به ذکر است که آنالیز استهلاکی با آنالیز در حالت میانگین متفاوت است و روش های آماری را شامل نمیشود. در واقع آنالیز استهلاکی زمان اجرای متوسط هر عمل در بدترین حالت را نشان میدهد.

برای این نوع آنالیز 3 روش مطرح است:

► آنالیز تجمعی Aggregate Analysis

► روش حسابرسی Accounting method

► روش پتانسیل Potential Method

 

♦ آنالیز تجمعی

در این روش هزینه n عمل را به دست می آوریم سپس به n تقسیم میکنیم. مثلا n عمل push، pop و Multipop(k) روی پشته s که در ابتدا خالی است انجام داده ایم (Multipop(k) ، k عنصر از پشته pop میکند. البته اگر از k عنصر در پشته باشند، همه عناصر pop میشوند) درست است که هزینه Multipop(k) ممکن است O(k) باشد ولی n عمل از عملیات فوق روه هم هزینه O(n) دارند پس هزینه هر عمل بصورت سرشکن شده برابر O(1) است.

 

♦ روش حسابرسی

در این روش به عملیات مختلف، شارژهای مختلفی نسبت میدهیم که ممکن است شارژی که نسبت میدهیم، از هزینه واقعی عمل کمتر یا بیشتر باشد. مقداری که یک عمل شارژ میشود را "هزینه استهلاک" آن عمل گویند.

اگر "هزینه استهلاک" یک عمل از هزینه واقعی آن عمل بیشتر باشد، تفاوت این دو بعنوان "اعتبار"  به عناصر خاصی از ساختمان داده تخصیص می یابد. این اعتبار را میتوان بعدا برای عملیاتی که هزینه استهلاکشان کمتر از هزینه واقعی شان است، صرف کرد.

 

♦ روش پتانسیل

روش قبلی، اعتبار را به عنصر تخصیص میداد ولی این روش ، اعتبار را به صورت پتانسیل به کل ساختمان داده تخصیص میدهد.

فرض کنید D0 وضعیت اولیه ساختمان داده ای است که میخواهیم n عمل روی آن انجام دهیم. Ci هزینه واقعی عمل i ام، Di وضعیت ساختمان داده است پس از انجام عمل i  ام روی Di-1 ، تابع پتانسیلی تعریف میکنیم به اسم ф که به هر وضعیت ساختمان داده، یک عدد حقیقی نسبت میدهد:

ф(Di)  یک عدد حقیقی =

بنابراین هزینه استهلاکی عمل i ام برابر است با :

C’i = Ci + ф(Di) - ф(Di-1)

 

 



0
نظرات

نظر خود را ارسال کنید



نام:
ایمیل:
دیدگاه:
captcha
کد امنیتی :


advertise
آنالیز استهلاکی برای تخمین هزینه الگوریتم ها آنالیز تجمعی Aggregate Analysisروش پتانسیل Potential Method الگوریتمروش حسابرسی Accounting method الگوریتمروشهای آنالیز استهلاکی الگوریتم هاآنالیز استهلاکی چیست؟انواع آنالیز استهلاکیآشنایی با روشهای آنالیز استهلاکی الگوریتم هاتبلیغات ارزان سایت آموزش برنامه نویسیتبلیغات مخصوص طراحان وب سایتتبلیغات در سایت برنامه نویسیتبلیغات اینترنتی برای برنامه نویساندر آغوش مینیمالیسممنوی همبرگر با سه خط افقی که روی یکدیگر قرار گرفته اند نشانه چیست؟ سوئیچ به یک ستون واحدتبدیل متن ساده به وبلاگ و سایت های پویا با React.jsکتابخانه sass برای استفاده آسان تر از آنکتابخانه سطح بالا برای اتوماتیک سازی اعمال مرورگر لیست برچسب ها
تمامی حقوق این سایت اعم از محتوی ، تصاویر ، قالب و ... متعلق به گروه مهندسی وب سایت سورس کد می باشد.
SourceCodes.ir ، افقی روشن برای برنامه نویسان ، از مبتدی تا حرفه ای

پیشنهادات ویژه سورس کد

پکیج ویژه پروژه پایانی رشته کامپیوتر دانلود مجموعه 70 پروژه کاربردی سی شارپ وب سایت فروشگاه با php