advertise laitec sharif univercity تبلیغات در سایت سورس کد تبلیغات در سایت سورس کد
دانلود پروژه معمای 8 با الگوریتم ژنتیک در سی شارپ

دانلود پروژه معمای 8 با الگوریتم ژنتیک در سی شارپ

3000 تومان
دانلود پروژه فروشنده دوره گرد با الگوریتم گرانشی در #C

دانلود پروژه فروشنده دوره گرد با الگوریتم گرانشی در #C

4800 تومان
پکیج ویژه پروژه پایانی و پایان نامه رشته کامپیوتر

پکیج ویژه پروژه پایانی و پایان نامه رشته کامپیوتر

45000 تومان
سورس پروژه پایانی وب سایت و نرم افزار کلینیک در ASP.net

سورس پروژه پایانی وب سایت و نرم افزار کلینیک در ASP.net

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

دانلود مجموعه 70 پروژه مفید و کاربردی سی شارپ #C

9500 تومان

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

در 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