Алгоритмдерді талдау әдісі: бизнес есептеріндегі «есептеу» әдісі. Осы әдіс операциялардың орташа құнын анықтауға көмектеседі, әсіресе O(1) шегін дәлелдеуде тиімді.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Амортизациялық талдау әдісі бизнес және қаржылық есептіліктің есептеу әдістері
Method of amortized analysis
accounting methods in business and financial reporting
Компьютерлік ғылымдағы алгоритмдерді талдау саласындағы есептеу әдісі – бухгалтерлік есеп негізіндегі амортизациялық талдау әдісі. Есептеу әдісі операцияның амортизацияланған құнын жиынтық талдау немесе потенциалды әдіспен салыстырғанда көбінесе түсініктірек көрсетеді. Дегенмен, мұндай талдаудың бірден айқын болатынына кепілдік жоқ; көбінесе есептеу әдісі үшін дұрыс параметрлерді таңдау, проблеманы және дәлелдеуге тырысылып жатқан күрделілік шегін білуді басқа екі әдіс сияқты талап етеді. Есептеу әдісі уақыт бойынша O(1) шегін дәлелдеуге ең қолайлы. Осы жерде түсіндірілген әдіс осындай шектеуді дәлелдеу үшін қолданылады.
In the field of analysis of algorithms in computer science, the accounting method is a method of amortized analysis based on accounting. The accounting method often gives a more intuitive account of the amortized cost of an operation than either aggregate analysis or the potential method. Note, however, that this does not guarantee such analysis will be immediately obvious; often, choosing the correct parameters for the accounting method requires as much knowledge of the problem and the complexity bounds one is attempting to prove as the other two methods. The accounting method is most naturally suited for proving an O(1) bound on time. The method as explained here is for proving such a bound.
Әдіс
Алгоритмде қолданылатын элементарлық операциялар жиынтығы таңдалады және олардың құны кездейсоқ түрде 1-ге тең деп белгіленеді. Бұл операциялардың нақты құны әртүрлі болуы мүмкін, бірақ бұл принципте ешқандай қиындық тудырмайды. Маңыздысы – әрбір элементарлық операцияның тұрақты құны болуы. Әрбір күрделі операцияға "төлем" тағайындалады. Бұл төлем аталған операцияны орындау үшін қажетті элементарлық операциялардың құнын жабуға арналған, ал қалған сома кейін пайдалану үшін резервке жиналады. Амортизациялық талдауды қажет ететін мәселелердің қиындығы сол, әдетте, кейбір операциялар тұрақты құннан артық шығынға түседі. Яғни, операцияның ең нашар жағдайындағы шығынын жабу үшін тұрақты төлем жеткіліксіз болады. Дегенмен, төлемді дұрыс таңдаған жағдайда, бұл қиындық жойлады; қымбат операциялар тек резервте олардың құнын жабуға жеткілікті төлем болғанда ғана орындалады.
A set of elementary operations which will be used in the algorithm is chosen and their costs are arbitrarily set to 1. The fact that the costs of these operations may differ in reality presents no difficulty in principle. What is important is that each elementary operation has a constant cost. Each aggregate operation is assigned a "payment". The payment is intended to cover the cost of elementary operations needed to complete this particular operation, with some of the payment left over, placed in a pool to be used later. The difficulty with problems that require amortized analysis is that, in general, some of the operations will require greater than constant cost. This means that no constant payment will be enough to cover the worst case cost of an operation, in and of itself. With proper selection of payment, however, this is no longer a difficulty; the expensive operations will only occur when there is sufficient payment in the pool to cover their costs.
Мысалдар
Бірнеше мысал есептеу әдісін түсіндіруге көмектеседі.
A few examples will help to illustrate the use of the accounting method.