| rdfs:comment
| - 計算機科学における 償却解析（しょうきゃくかいせき、英: amortized analysis）またはならし解析とは、与えられたアルゴリズムの複雑性あるいは計算機資源（特に時間またはメモリ）をどれだけ必要とするかを分析する手法である。償却解析の動機は、一回の実行あたりの最悪実行時間を見ることがあまりにも悲観的であるということである。与えられたアルゴリズムの一定の動作は著しく計算資源を消費するかもしれないし、他の動作はそれほど消費しないかもしれない。償却分析はアルゴリズムの一連の動作全体にわたってコストが高い、またはそうでもない動作の両方を考慮する。これは、その性能に影響を与える要素(入力の種類、入力の長さなど)の説明を含んでもよい。 (ja)
- Амортизационный анализ — это метод анализа вычислительной сложности алгоритма, используемый в случаях когда время исполнения одного шага алгоритма, умноженное на число шагов, даёт слишком большую оценку на время исполнения всего алгоритма по сравнению с тем, какая она на самом деле. (ru)
- في علم الحاسوب، فإن عملية تحليل استهلاك الدين هي طريقة لتحليل ودراسة تعقيد خوارزمية معينة كحساب تكلفة تنفيذ الخوارزمية بناءً على معايير مختلفة مثل الوقت الذي تحتاجه الخوارزمية لإنهاء التنفيذ أو المساحة التي تحتاجها لتخزين قيم العناصر والمتغيرات أثناء التنفيذ. الهدف من استخدام تحليل استهلاك الدين هو أن في كثير من الأحيان تكون التكلفة الناتجة من تحليل أسوأ الحالات مبالغاً فيها جدا، ونادرا ما يتم الحاجة إلى هذه التكلفة لتنفيد الخوارزمية. ولذلك فإن تحليل استهلاك الدين تقوم على حساب متوسط الوقت الذي تحتاجه الخوارزمية لإنهاء تنفيذ مجموعة من العمليات التي يتم تنفيذها بشكل متسلسل. يجب الأخذ بعين الاعتبار بأن عملية تحليل استهلاك الدين تختلف عن عملية إيجاد متوسط التعقيد التي تعتمد على فرضية الاحتمالات لهياكل البيانات والعمليات التي تستخدمها الخوارزمية. ولهذا السبب فإن عملية تحليل استهلاك الدين تعتبر (ar)
- In computer science, amortized analysis is a method for analyzing a given algorithm's complexity, or how much of a resource, especially time or memory, it takes to execute. The motivation for amortized analysis is that looking at the worst-case run time can be too pessimistic. Instead, amortized analysis averages the running times of operations in a sequence over that sequence.As a conclusion: "Amortized analysis is a useful tool that complements other techniques such as worst-case and average-case analysis." (en)
- En ciencias de la computación, especialmente el análisis de algoritmos, el análisis de amortización considera el promedio de tiempo de ejecución por más de una operación en el peor de los casos, la secuencia de las operaciones. El análisis de amortización difiere del promedio de rendimiento en caso de que no se trate de probabilidad; el análisis de amortización garantiza la operación por más tiempo tomando en cuenta el peor de los casos en el rendimiento. Existen varias técnicas utilizadas en el análisis amortizado: (es)
- In der theoretischen Informatik betrachtet die amortisierte Laufzeitanalyse die Kosten von Operationen in Abfolgen («sequences») dieser Operation. Im Unterschied zur allgemeinen Laufzeitanalyse werden nicht die maximalen Kosten einzelner Schritte betrachtet, sondern es wird die obere Schranke aller Summen der Laufzeiten mehrerer Durchläufe der Operation analysiert und diese Summen durch die Anzahl der Operationen im Durchlauf dividiert, so dass ein Durchschnitt herauskommt, der als Aufwand für die untersuchte Operation genommen wird. Dies kann – beispielsweise bei Fibonacci-Heaps – zu einem besseren Wert führen, da es häufig Operationen gibt, die zwar im Einzelfall teuer sein können, wobei aber ein „teurer“ Fall verglichen mit den anderen (günstigeren) Fällen in einem Ablauf relativ selten (de)
- En informatique, l'analyse amortie est une méthode d'évaluation de la complexité temporelle des opérations sur une structure de données. Cette analyse résulte en une classification des algorithmes et conduit à une théorie spécifique de la complexité des algorithmes que l'on appelle complexité amortie. (fr)
- 컴퓨터 공학에서, 분할상환분석 (amortized analysis)은 주어진 알고리즘의 시간 복잡도나 프로그램을 수행하는데 소요되는 시간 또는 메모리 같은 자원 사용량을 분석하기 위해서 사용하는 기법이다.알고리즘을 분석할 때에 각각의 연산마다 최악의 경우를 따져본다는 것은 굉장히 힘든 일이기 때문에, 이를 쉽게 해결하기 위해 분할상환분석이라는 방법론이 나오게 되었다. (ko)
- Na ciência da computação, análise amortizada é um método para analisar a complexidade de tempo de um algoritmo ou quantos recursos computacionais, especialmente de tempo ou de memória no contexto de programas de computadores, ele leva para executar. Diferente das outras análises que focam no tempo de execução no pior caso, a análise amortizada examina como um algoritmo irá se comportar na prática ou na média. (pt)
- Koszt zamortyzowany – miara złożoności obliczeniowej operacji na strukturze danych. Koszt zamortyzowany operacji jest średnim czasem wykonania przypadającym na jedną operację w pesymistycznym ciągu operacji. Analiza kosztu zamortyzowanego zajmuje się oszacowaniem czasu niezbędnego do wykonania ciągu operacji, a nie pojedynczej operacji. Może się bowiem zdarzyć, że wykonanie całego ciągu jest mniej kosztowne niż wskazywałaby na to złożoność obliczeniowa jednej operacji, ponieważ tylko niektóre ciągi operacji są możliwe. (pl)
- Амортизаційний аналіз — метод аналізу швидкодії алгоритмів, що розглядає усю послідовність операцій виконуваних програмою. Тут ми усереднюємо час необхідний для виконання операції над певною структурою даних. З амортизаційним аналізом ми можемо показати, що середній час необхідний на одну операцію нетривалий, хоча певні операції у послідовності вимагають багато часу. Амортизаційний аналіз відрізняється від аналізу середнього випадку тим, що ймовірність не має значення; амортизаційний аналіз гарантує середню швидкодію кожної операції в найгіршому випадку. Прикладами структур даних чиї операцію аналізуються за допомогою амортизаційного аналізу є геш-таблиці, неперетинні множини, розширювані дерева. (uk)
- 平攤分析在计算机科学中，是用於算法分析中的方法，平攤分析常用於分析資料結構（動態的資料結構），在使用平攤分析前須知道資料結構各種操作所可能發生的時間，並計算出最壞情况下的操作情況並加以平均，得到操作的平均耗费时間。平摊分析只能確保最坏情况性能的每次操作耗费的平均时间，並不能確認平均情况性能。 一個簡單的例子，一個長度為n的list，在list的最後要加入一筆新的資料此時要花費的操作時間為O(n)，此時也是加入新的資料的最糟糕的情況。但是，一个 n 个插入的操作序列仍然可以在 O(n) 的时间内完成，因为剩下的插入可以在常数时间内完成，因此n 个插入可以在 O(n) 的时间内完成。因此每操作的平摊耗费为O(n) / n = O(1)。 注意平摊分析与平均时间分析和概率算法的概率分析不同。在平均时间分析中，我们平均化所有可能的输入；在概率算法的概率分析中，我们平均化所有可能的随机选择；在平摊分析中，我们平均化一系列操作的耗费。平摊分析假设的是最坏情况输入并且通常不运行随机选择。 平摊分析中几种常用的技术: (zh)
|
| has abstract
| - في علم الحاسوب، فإن عملية تحليل استهلاك الدين هي طريقة لتحليل ودراسة تعقيد خوارزمية معينة كحساب تكلفة تنفيذ الخوارزمية بناءً على معايير مختلفة مثل الوقت الذي تحتاجه الخوارزمية لإنهاء التنفيذ أو المساحة التي تحتاجها لتخزين قيم العناصر والمتغيرات أثناء التنفيذ. الهدف من استخدام تحليل استهلاك الدين هو أن في كثير من الأحيان تكون التكلفة الناتجة من تحليل أسوأ الحالات مبالغاً فيها جدا، ونادرا ما يتم الحاجة إلى هذه التكلفة لتنفيد الخوارزمية. ولذلك فإن تحليل استهلاك الدين تقوم على حساب متوسط الوقت الذي تحتاجه الخوارزمية لإنهاء تنفيذ مجموعة من العمليات التي يتم تنفيذها بشكل متسلسل. يجب الأخذ بعين الاعتبار بأن عملية تحليل استهلاك الدين تختلف عن عملية إيجاد متوسط التعقيد التي تعتمد على فرضية الاحتمالات لهياكل البيانات والعمليات التي تستخدمها الخوارزمية. ولهذا السبب فإن عملية تحليل استهلاك الدين تعتبر طريقة مهمة ومكملة لطريقتي التحليل بأسوأ الحالات وتحليل متوسط التعقيد. تكلفة كل عملية من مجموعة متسلسلة من العمليات تختلف بناءً على مجموعة من العوامل مثل نوع هيكلة البيانات المستخدمة لتنفيذ الخوارزمية بحيث بعضها يتحاج إلى تكلفة أعلى من غيرها وبعضها الأخر يحتاج إلى تكلفة أقل. لذلك فإن إيجاد التكلفة باستخدام طريقة تحليل استهلاك الدين قائمة على تحديد العمليات الأكثر والأقل تكلفة من مجموعة متسلسلة من العمليات، وهذا قد يتطلب مراعاة طبيعة البيانات المدخلة وحجمها وغيرها من العوامل التي تؤثر على أداء الخوارزمية. (ar)
- In der theoretischen Informatik betrachtet die amortisierte Laufzeitanalyse die Kosten von Operationen in Abfolgen («sequences») dieser Operation. Im Unterschied zur allgemeinen Laufzeitanalyse werden nicht die maximalen Kosten einzelner Schritte betrachtet, sondern es wird die obere Schranke aller Summen der Laufzeiten mehrerer Durchläufe der Operation analysiert und diese Summen durch die Anzahl der Operationen im Durchlauf dividiert, so dass ein Durchschnitt herauskommt, der als Aufwand für die untersuchte Operation genommen wird. Dies kann – beispielsweise bei Fibonacci-Heaps – zu einem besseren Wert führen, da es häufig Operationen gibt, die zwar im Einzelfall teuer sein können, wobei aber ein „teurer“ Fall verglichen mit den anderen (günstigeren) Fällen in einem Ablauf relativ selten vorkommt. Ein anderes Beispiel, dessen Untersuchung 1978 (noch vor der Namensgebung «amortized») stattfand, beschreibt die Anzahl der Rebalancierungsoperationen in BB[α]-Bäumen als amortisiert konstant. Damit wird die amortisierte Laufzeitanalyse («amortized analysis») als dritte Technik neben die bekannten Laufzeitanalysen der maximalen Kosten («worst-case analysis») und des durchschnittlichen Verhaltens («average-case analysis») gestellt. Bei der amortisierten Laufzeitanalyse gibt es drei prinzipiell gleichwertige Methoden:
* die Aggregat-Methode
* die Account-Methode (auch Bankkonto-Paradigma genannt)
* die Potentialfunktionmethode (de)
- In computer science, amortized analysis is a method for analyzing a given algorithm's complexity, or how much of a resource, especially time or memory, it takes to execute. The motivation for amortized analysis is that looking at the worst-case run time can be too pessimistic. Instead, amortized analysis averages the running times of operations in a sequence over that sequence.As a conclusion: "Amortized analysis is a useful tool that complements other techniques such as worst-case and average-case analysis." For a given operation of an algorithm, certain situations (e.g., input parametrizations or data structure contents) may imply a significant cost in resources, whereas other situations may not be as costly. The amortized analysis considers both the costly and less costly operations together over the whole sequence of operations. This may include accounting for different types of input, length of the input, and other factors that affect its performance. (en)
- En ciencias de la computación, especialmente el análisis de algoritmos, el análisis de amortización considera el promedio de tiempo de ejecución por más de una operación en el peor de los casos, la secuencia de las operaciones. El análisis de amortización difiere del promedio de rendimiento en caso de que no se trate de probabilidad; el análisis de amortización garantiza la operación por más tiempo tomando en cuenta el peor de los casos en el rendimiento. El método requiere el conocimiento de esta serie de operaciones que son posibles. Este es el caso más común en estructuras de datos, que han estado que persiste entre las operaciones. La idea básica es que el peor de los casos la operación puede alterar el estado de tal manera que el peor de los casos no puede ocurrir de nuevo por un largo tiempo, por lo tanto queda "amortizado" su costo. Como ejemplo simple, en una implementación específica de array dinámicos, doblamos el tamaño del array cada vez que se rellene. Debido a esto, es necesario reasignar el array, y en el peor de los casos puede requerir una inserción O (n). Sin embargo, una secuencia de n inserciones siempre se puede hacer en O (n) tiempo, de modo que el tiempo de amortización por operación es O (n) / n = O (1). El análisis del caso promedio y análisis probabilístico no son lo mismo en análisis de amortización. En análisis del caso promedio, estamos en un promedio de todas las posibles entradas, en el análisis probabilístico, estamos en un promedio de todas las posibles opciones al azar; en el análisis de amortización, estamos en promedio más de una secuencia de operaciones. Amortizan análisis asume el peor de los casos de entrada y, normalmente, no permite opciones al azar. Existen varias técnicas utilizadas en el análisis amortizado:
* Análisis global determina el límite superior T (n) en el coste total de una secuencia de n operaciones, y luego calcula el coste medio a T (n) / n.
* Método Contable permite determinar el costo individual de cada operación, que combina su inmediato tiempo de ejecución y su influencia en el tiempo de ejecución de las futuras operaciones. Generalmente, muchos operaciones de corta duración acumulan una "deuda" de situación desfavorable en pequeños incrementos, mientras que las operaciones de larga duración disminuyen drásticamente.
* Método potencial es como el método, pero las operaciones tempranas que sobrecargan la cuente pueden ser compensadas cobrando menos de la cuenta más tarde. (es)
- En informatique, l'analyse amortie est une méthode d'évaluation de la complexité temporelle des opérations sur une structure de données. Cette analyse résulte en une classification des algorithmes et conduit à une théorie spécifique de la complexité des algorithmes que l'on appelle complexité amortie. L'analyse amortie consiste essentiellement à majorer le coût cumulé d'une suite d'opérations pour attribuer à chaque opération la moyenne de cette majoration, en prenant en compte le fait que les cas chers surviennent rarement et isolément et compensent les cas bon marché. Pour être utilisable, cette analyse suppose que l'on est capable de borner la fréquence des cas les plus coûteux. L'analyse amortie se place dans le cas le plus défavorable et garantit la performance moyenne de chaque opération dans ce cas. À partir de l'analyse amortie on peut concevoir des structures de données efficaces. (fr)
- 計算機科学における 償却解析（しょうきゃくかいせき、英: amortized analysis）またはならし解析とは、与えられたアルゴリズムの複雑性あるいは計算機資源（特に時間またはメモリ）をどれだけ必要とするかを分析する手法である。償却解析の動機は、一回の実行あたりの最悪実行時間を見ることがあまりにも悲観的であるということである。与えられたアルゴリズムの一定の動作は著しく計算資源を消費するかもしれないし、他の動作はそれほど消費しないかもしれない。償却分析はアルゴリズムの一連の動作全体にわたってコストが高い、またはそうでもない動作の両方を考慮する。これは、その性能に影響を与える要素(入力の種類、入力の長さなど)の説明を含んでもよい。 (ja)
- 컴퓨터 공학에서, 분할상환분석 (amortized analysis)은 주어진 알고리즘의 시간 복잡도나 프로그램을 수행하는데 소요되는 시간 또는 메모리 같은 자원 사용량을 분석하기 위해서 사용하는 기법이다.알고리즘을 분석할 때에 각각의 연산마다 최악의 경우를 따져본다는 것은 굉장히 힘든 일이기 때문에, 이를 쉽게 해결하기 위해 분할상환분석이라는 방법론이 나오게 되었다. 어떠한 임의의 알고리즘에 대해서, 어떤 연산은 자원적 측면에서 상당한 비용을 소모할 수 있지만, 반면 다른 연산은 그렇게 고비용을 소모하지 않을 수 있다. 분할상환 분석은 알고리즘의 전반적인 연산 집합에 대해 비용이 높은 연산, 그리고 비용이 덜한 연산 모두를 함께 고려하는 기법이라 하겠다. 이것은 다른 종류의 입력, 입력의 길이, 이 알고리즘의 성능에 영향을 미치는 다른 요인들을 전부 고려한다. 수행된 모든 연산에 대해 자료구조 연산만의 어떤 시퀀스를 수행하는데 필요한 시간의 평균을 구한다. 비록 그 시퀀스에서 하나의 연산비용이 비싸더라도, 그 일련의 연산에 대해 평균을 구하면 연산 하나의 평균 비용이 작다는 것을 분할 상환 분석을 이용해 보일 수 있다. 분할 상환 분석은 확률이 포함되지 않으므로 평균비용 분석과는 다르다. 분할 상환 분석은 최악의 경우에도 각 연산의 평균 수행성능을 보장한다. (ko)
- Koszt zamortyzowany – miara złożoności obliczeniowej operacji na strukturze danych. Koszt zamortyzowany operacji jest średnim czasem wykonania przypadającym na jedną operację w pesymistycznym ciągu operacji. Analiza kosztu zamortyzowanego zajmuje się oszacowaniem czasu niezbędnego do wykonania ciągu operacji, a nie pojedynczej operacji. Może się bowiem zdarzyć, że wykonanie całego ciągu jest mniej kosztowne niż wskazywałaby na to złożoność obliczeniowa jednej operacji, ponieważ tylko niektóre ciągi operacji są możliwe. Koszt zamortyzowany różni się od kosztu średniego tym, że bierze pod uwagę ciąg operacji i nie jest metodą probabilistyczną. O ile koszt średni reprezentuje wartość oczekiwaną złożoności czasowej operacji, tak koszt zamortyzowany stanowi oszacowany dla pesymistycznego przypadku średniego koszt operacji w ciągu. (pl)
- Na ciência da computação, análise amortizada é um método para analisar a complexidade de tempo de um algoritmo ou quantos recursos computacionais, especialmente de tempo ou de memória no contexto de programas de computadores, ele leva para executar. Diferente das outras análises que focam no tempo de execução no pior caso, a análise amortizada examina como um algoritmo irá se comportar na prática ou na média. Enquanto certas operações de um dado algoritmo tenham um grande custo em recursos, outras operações talvez não sejam tão custosas. A análise amortizada considera os dois tipos de operações juntos. Isso pode cobrir tipos diferentes de dados de entrada, tamanho da entrada, e outros fatores que afetam o desempenho do algoritmo. (pt)
- Амортизаційний аналіз — метод аналізу швидкодії алгоритмів, що розглядає усю послідовність операцій виконуваних програмою. Тут ми усереднюємо час необхідний для виконання операції над певною структурою даних. З амортизаційним аналізом ми можемо показати, що середній час необхідний на одну операцію нетривалий, хоча певні операції у послідовності вимагають багато часу. Амортизаційний аналіз відрізняється від аналізу середнього випадку тим, що ймовірність не має значення; амортизаційний аналіз гарантує середню швидкодію кожної операції в найгіршому випадку. Прикладами структур даних чиї операцію аналізуються за допомогою амортизаційного аналізу є геш-таблиці, неперетинні множини, розширювані дерева. Амортизаційний аналіз початково виник з методу відомого як агрегаційний аналіз або метод групування, який наразі є одним зі способів проведення амортизаційного аналізу. Однак, формально, техніка була представлена Робертом Тар'яном у його документі 1985 року Амортизована складність обчислень, який висвітлював більш корисний різновид аналізу ніж звичайний імовірнісний аналіз. (uk)
- Амортизационный анализ — это метод анализа вычислительной сложности алгоритма, используемый в случаях когда время исполнения одного шага алгоритма, умноженное на число шагов, даёт слишком большую оценку на время исполнения всего алгоритма по сравнению с тем, какая она на самом деле. (ru)
- 平攤分析在计算机科学中，是用於算法分析中的方法，平攤分析常用於分析資料結構（動態的資料結構），在使用平攤分析前須知道資料結構各種操作所可能發生的時間，並計算出最壞情况下的操作情況並加以平均，得到操作的平均耗费时間。平摊分析只能確保最坏情况性能的每次操作耗费的平均时间，並不能確認平均情况性能。 一個簡單的例子，一個長度為n的list，在list的最後要加入一筆新的資料此時要花費的操作時間為O(n)，此時也是加入新的資料的最糟糕的情況。但是，一个 n 个插入的操作序列仍然可以在 O(n) 的时间内完成，因为剩下的插入可以在常数时间内完成，因此n 个插入可以在 O(n) 的时间内完成。因此每操作的平摊耗费为O(n) / n = O(1)。 注意平摊分析与平均时间分析和概率算法的概率分析不同。在平均时间分析中，我们平均化所有可能的输入；在概率算法的概率分析中，我们平均化所有可能的随机选择；在平摊分析中，我们平均化一系列操作的耗费。平摊分析假设的是最坏情况输入并且通常不运行随机选择。 平摊分析中几种常用的技术:
* 聚合分析决定 n 个操作序列的耗费上界T(n)，然后计算平均耗费为 T(n) / n。
* 记账方法确定每个操作的耗费，结合它的直接执行时间及它在对运行时中未来操作的影响。通常来说，许多短操作增量累加成「债」，而通过减少长操作的次数来「偿还」。
* 势能方法类似记账方法，但通过预先储蓄「势能」而在需要的时候释放。 (zh)
|
![[RDF Data]](/fct/images/sw-rdf-blue.png)
![[cxml]](/fct/images/cxml_doc.png)
![[csv]](/fct/images/csv_doc.png)
![[text]](/fct/images/ntriples_doc.png)
![[turtle]](/fct/images/n3turtle_doc.png)
![[ld+json]](/fct/images/jsonld_doc.png)
![[rdf+json]](/fct/images/json_doc.png)
![[rdf+xml]](/fct/images/xml_doc.png)
![[atom+xml]](/fct/images/atom_doc.png)
![[html]](/fct/images/html_doc.png)
