| rdfs:comment
| - Master theorem (často také Kuchařková věta nebo Mistrovská metoda), což je speciální případ , poskytuje při analýze složitosti algoritmů kuchařkové řešení asymptotické složitosti pro často používané . Byl popularizován knihou napsanou , , Rivestem a , kde je uveden a dokázán v sekcích 4.3 a 4.4. (cs)
- في تحليل الخوارزميات، تُقدم النظرية الرئيسة لتواترات فرق تسد (بالإنجليزية: master theorem for divide-and-conquer recurrences) (باستخدام ترميز أوه الكبير) للعلاقات التواترية التي تحدث في الكثير من خوارزميات فرق تسد. تم طرح هذه الطريقة لأول مرة في عام 1980م من قبل جون بنتلي، و، و. ووُصفت على أنها طريقة موحدة لحل تواترات معينة. روج اسم هذه الطريقة (النظرية الرئيسة) كتاب مقدمة في الخوارزميات. لا يمكن حل جميع التواترات بهذه النظرية؛ وتوفر تعميماً أكبر. (ar)
- Το μάστερ θεώρημα (master theorem) είναι ειδική περίπτωση του . Χρησιμοποιείται στην για τον προσδιορισμό του μιας . Ωστόσο δεν επιλύεται κάθε αναδρομική σχέση με το μάστερ θεώρημα. (el)
- Der Hauptsatz der Laufzeitfunktionen – oder oft auch aus dem Englischen als Master-Theorem entlehnt – ist ein Spezialfall des Akra-Bazzi-Theorems und bietet eine schnelle Lösung für die Frage, in welcher Laufzeitklasse eine gegebene rekursiv definierte Funktion liegt. Mit dem Master-Theorem kann allerdings nicht jede rekursiv definierte Funktion gelöst werden. Lässt sich keiner der drei möglichen Fälle des Master-Theorems auf die Funktion T anwenden, so muss man die Komplexitätsklasse der Funktion anderweitig berechnen. (de)
- En el análisis de algoritmos, el teorema maestro proporciona una solución sencilla en términos asintóticos (usando una Cota superior asintótica) para que ocurren en muchos algoritmos recursivos tales como en el Algoritmo divide y vencerás. Fue popularizado por el libro Introducción a los algoritmos por Cormen, Leiserson, Rivest, y Stein, en el cual fue tanto introducido como probado formalmente. No todas las ecuaciones de recurrencia pueden ser resueltas con el uso del teorema maestro. (es)
- 알고리즘 분석에서 The Master Method(마스터 방법, 만능 방법), Master Theorem(마스터 정리)는 으로 표현한 알고리즘의 동작 시간을 점근적으로 계산하여 간단하게 계산하는 방법이다. 잘 알려진 알고리즘 교과서 Introduction to Algorithms의 4.3절과 4.4절, 4.5절에 설명되어 유명해졌으나, 이 방법이 모든 재귀 관계식을 풀 수 있는 건 아니다. 다음과 같은 관계식이 주어졌다고 하자. 여기서 이고 은 점근적으로 양수 함수값을 가지는 함수이다. 이때 다음과 같은 경우에 대해 점근적 수행 시간을 계산할 수 있다. 1.
* 만약 어떤 상수 에 대해 이면, 이다. 2.
* 만약 이면, 이다. 3.
* 만약 어떤 상수 에 대해 이고, 과 충분히 큰 에 대해 이 성립하면, 이다. (ko)
- Het master-theorem biedt een methode (master-method) die het bepalen van de van recurrente betrekkingen in de algoritmiek gemakkelijk maakt. Het master-theorem kan echter niet de complexiteit van alle recurrente betrekkingen bepalen. (nl)
- Twierdzenie o rekurencji uniwersalnej jest twierdzeniem matematycznym pozwalającym w łatwy sposób znajdować ograniczenie asymptotyczne pewnej klasy funkcji zdefiniowanych rekurencyjnie. (pl)
- Майстер-метод (англ. master theorem, master method) надає готові розв'язки в асимптотичному записі (через використання нотації великого О) для рекурентних співвідношень які використовуються при аналізі алгоритмів «розділяй і володарюй». Його популяризувала канонічна книга з алгоритмів — Вступ в алгоритми, написана Томасом Корменом, Чарльзом Лейзерсоном, Рівестом і , в якій метод описано і доведено. Однак, не всі рекурентні співвідношення можна розв’язати за допомогою цього методу; узагальнює майстер-метод. (uk)
- 在演算法分析中，主定理（英語：master theorem）提供了用渐近符号（大O符号）表示许多由分治法得到的递推关系式的方法。这种方法最初由，和在1980年提出，在那里被描述为解决这种递推的“天下無敵法”(master method)。此方法经由经典演算法教科书，，和Stein的《算法导论》 (introduction to algorithm) 推广而为人熟知。 不过，并非所有递推关系式都可应用支配理论。该定理的推广形式包括。 (zh)
- In the analysis of algorithms, the master theorem for divide-and-conquer recurrences provides an asymptotic analysis (using Big O notation) for recurrence relations of types that occur in the analysis of many divide and conquer algorithms. The approach was first presented by Jon Bentley, Dorothea Blostein (née Haken), and James B. Saxe in 1980, where it was described as a "unifying method" for solving such recurrences. The name "master theorem" was popularized by the widely used algorithms textbook Introduction to Algorithms by Cormen, Leiserson, Rivest, and Stein. (en)
- En informatique, et plus particulièrement en analyse de la complexité des algorithmes, le master theorem ou théorème sur les récurrences de partition permet d'obtenir une solution en termes asymptotiques (en utilisant les notations en O) pour des relations de récurrence d'un certain type rencontrées dans l'analyse de complexité d'algorithmes qui sont régis par le paradigme diviser pour régner. (fr)
- Il teorema dell'esperto, noto anche come teorema principale (in inglese master theorem) o teorema del maestro, è un teorema inerente all'analisi degli algoritmi che fornisce una soluzione asintotica ad una famiglia di relazioni di ricorrenza. È stato inizialmente esposto da Jon Bentley, , e nel 1980, dove fu descritto come un metodo unificato per una famiglia di ricorrenze. Il nome di questo teorema è stato popolarizzato dal famoso manuale Introduzione agli algoritmi di Cormen, , Rivest e . Non fornisce una soluzione a tutte le possibili relazioni di ricorrenza, ed una sua generalizzazione è il teorema di Akra-Bazzi. (it)
- Na análise de algoritmos, o teorema mestre para recorrências de divisão e conquista fornece uma análise assintótica (usando a notação Grande-O) para relações de recorrência que ocorrem na análise de muitos algoritmos de divisão e conquista. A abordagem foi apresentada pela primeira vez por Jon Bentley, Dorothea Haken, e James B. Saxe , em 1980, onde foi descrito como um "método unificador" para a solução de tais recorrências. O nome "teorema mestre" foi popularizado pelo livro de algoritmos amplamente utilizado Algoritmos: teoria e prática por Cormen, Leiserson, Rivest e Stein. (pt)
- Основная теорема о рекуррентных соотношениях (англ. Master theorem) используется в анализе алгоритмов для получения асимптотической оценки рекурсивных соотношений (рекуррентных уравнений), часто возникающих при анализе алгоритмов типа «разделяй и властвуй» (divide and conquer), например, при оценке времени их выполнения. Теорема была введена и доказана Джоном Бентли, Доротеном Хакеном и Джеймсом Хакеном в 1980 году. Теорема была популяризована в книге Алгоритмы: построение и анализ (Томас Кормен, Чарльз Лейзерстон, Рональд Ривест, Клиффорд Штайн), в которой она была приведена. (ru)
|
![[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)
