گروه تلگرامی برنامه نویسان advertise ساخت اپلیکیشن آندروید و IOS و اپ ساز laitec sharif univercity
دانلود پروژه مهندسی نرم افزار ، سیستم داروخانه

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

3000 تومان
دانلود پروژه وب سایت هتل با HTML و ASP.NET

دانلود پروژه وب سایت هتل با HTML و ASP.NET

4900 تومان
دانلود پروژه آموزش چندرسانه ای با دایرکتور Director

دانلود پروژه آموزش چندرسانه ای با دایرکتور Director

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

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

3000 تومان
دانلود برنامه هشت وزیر با جستجوی عمقی در سی شارپ

دانلود برنامه هشت وزیر با جستجوی عمقی در سی شارپ

3000 تومان

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

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

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

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