Master theorem (analysis of algorithms) (original) (raw)
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.
| Property | Value |
|---|---|
| dbo:abstract | 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) 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. Not all recurrence relations can be solved with the use of this theorem; its generalizations include the Akra–Bazzi method. (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. L'énoncé sur les expressions asymptotiques de ces récurrences a été nommé « master theorem » dans la version anglaise du manuel Introduction to Algorithms de Cormen, Leiserson, Rivest et Stein; dans sa traduction française, le théorème est appelé le « théorème général ». L'approche a été présentée notamment en 1980 par Jon Bentley, Dorothea Haken, et James B. Saxe. Le théorème couvre un certain nombre de types de récurrences ; une extension à d'autres expressions est fournie par ce que l’on appelle la méthode d'Akra-Bazzi. (fr) 알고리즘 분석에서 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) 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. Informalmente, il teorema afferma che, data una relazione di ricorrenza nella forma con e , in alcuni casi si può ottenere una soluzione confrontando con la funzione . Se è asintoticamente polinomialmente più piccola (ovvero più piccola per almeno un fattore polinomiale allora ; se le due funzioni hanno asintoticamente la stessa grandezza allora ; infine, se è sufficientemente regolare e polinomialmente più grande allora . Non sono coperti dal teorema i casi in cui sia asintoticamente più grande o più piccola di in modo non polinomiale. (it) Twierdzenie o rekurencji uniwersalnej jest twierdzeniem matematycznym pozwalającym w łatwy sposób znajdować ograniczenie asymptotyczne pewnej klasy funkcji zdefiniowanych rekurencyjnie. (pl) 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. Nem todas as relações de recorrência podem ser resolvidas com o uso do teorema; suas generalizações incluem o método de Akra-Bazzi. (pt) Основная теорема о рекуррентных соотношениях (англ. Master theorem) используется в анализе алгоритмов для получения асимптотической оценки рекурсивных соотношений (рекуррентных уравнений), часто возникающих при анализе алгоритмов типа «разделяй и властвуй» (divide and conquer), например, при оценке времени их выполнения. Теорема была введена и доказана Джоном Бентли, Доротеном Хакеном и Джеймсом Хакеном в 1980 году. Теорема была популяризована в книге Алгоритмы: построение и анализ (Томас Кормен, Чарльз Лейзерстон, Рональд Ривест, Клиффорд Штайн), в которой она была приведена. Не все рекурсивные соотношения могут быть решены с помощью основной теоремы. Существует несколько её обобщений, в том числе Akra-Bazzi method. (ru) Майстер-метод (англ. master theorem, master method) надає готові розв'язки в асимптотичному записі (через використання нотації великого О) для рекурентних співвідношень які використовуються при аналізі алгоритмів «розділяй і володарюй». Його популяризувала канонічна книга з алгоритмів — Вступ в алгоритми, написана Томасом Корменом, Чарльзом Лейзерсоном, Рівестом і , в якій метод описано і доведено. Однак, не всі рекурентні співвідношення можна розв’язати за допомогою цього методу; узагальнює майстер-метод. (uk) 在演算法分析中，主定理（英語：master theorem）提供了用渐近符号（大O符号）表示许多由分治法得到的递推关系式的方法。这种方法最初由，和在1980年提出，在那里被描述为解决这种递推的“天下無敵法”(master method)。此方法经由经典演算法教科书，，和Stein的《算法导论》 (introduction to algorithm) 推广而为人熟知。 不过，并非所有递推关系式都可应用支配理论。该定理的推广形式包括。 (zh) |
| dbo:thumbnail | wiki-commons:Special:FilePath/Recursive_problem_solving.svg?width=300 |
| dbo:wikiPageExternalLink | https://www.blogcyberini.com/2017/11/teorema-mestre.html |
| dbo:wikiPageID | 561585 (xsd:integer) |
| dbo:wikiPageLength | 15914 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1122572444 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Ron_Rivest dbr:Jon_Bentley_(computer_scientist) dbr:Introduction_to_Algorithms dbr:Thomas_H._Cormen dbr:Analysis_of_algorithms dbr:Clifford_Stein dbc:Theorems_in_computational_complexity_theory dbr:Michael_T._Goodrich dbr:Roberto_Tamassia dbc:Asymptotic_analysis dbr:Akra–Bazzi_method dbc:Recurrence_relations dbr:Recurrence_relation dbr:James_B._Saxe dbr:Asymptotic_analysis dbr:Asymptotic_complexity dbc:Analysis_of_algorithms dbr:Charles_E._Leiserson dbr:Big_O_notation dbr:Divide_and_conquer_algorithm dbr:Dorothea_Blostein dbr:Merge_sort dbr:Asymptotically_tight_bound dbr:Akra–Bazzi_theorem dbr:Recursive_algorithm dbr:Binary_search dbr:Ronald_L._Rivest dbr:File:Recursive_problem_solving.svg dbr:Solution_tree |
| dbp:wikiPageUsesTemplate | dbt:! dbt:For dbt:ISBN dbt:In_lang dbt:Math dbt:Mvar dbt:Reflist dbt:Short_description |
| dct:subject | dbc:Theorems_in_computational_complexity_theory dbc:Asymptotic_analysis dbc:Recurrence_relations dbc:Analysis_of_algorithms |
| 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) |
| rdfs:label | النظرية الرئيسة (تحليل الخوارزميات) (ar) Master theorem (cs) Master-Theorem (de) Μάστερ Θεώρημα (el) Teorema maestro (es) Master theorem (fr) Teorema dell'esperto (it) Master theorem (analysis of algorithms) (en) 마스터 정리 (ko) Master-theorem (nl) Twierdzenie o rekurencji uniwersalnej (pl) Teorema mestre (análise de algoritmos) (pt) Основная теорема о рекуррентных соотношениях (ru) 主定理 (zh) Майстер-метод (uk) |
| owl:sameAs | wikidata:Master theorem (analysis of algorithms) dbpedia-ar:Master theorem (analysis of algorithms) dbpedia-cs:Master theorem (analysis of algorithms) dbpedia-de:Master theorem (analysis of algorithms) dbpedia-el:Master theorem (analysis of algorithms) dbpedia-es:Master theorem (analysis of algorithms) dbpedia-fa:Master theorem (analysis of algorithms) dbpedia-fr:Master theorem (analysis of algorithms) dbpedia-he:Master theorem (analysis of algorithms) dbpedia-hu:Master theorem (analysis of algorithms) dbpedia-it:Master theorem (analysis of algorithms) dbpedia-ko:Master theorem (analysis of algorithms) dbpedia-nl:Master theorem (analysis of algorithms) dbpedia-pl:Master theorem (analysis of algorithms) dbpedia-pt:Master theorem (analysis of algorithms) dbpedia-ru:Master theorem (analysis of algorithms) dbpedia-sr:Master theorem (analysis of algorithms) dbpedia-uk:Master theorem (analysis of algorithms) dbpedia-zh:Master theorem (analysis of algorithms) https://global.dbpedia.org/id/551X8 |
| prov:wasDerivedFrom | wikipedia-en:Master_theorem_(analysis_of_algorithms)?oldid=1122572444&ns=0 |
| foaf:depiction | wiki-commons:Special:FilePath/Recursive_problem_solving.svg |
| foaf:isPrimaryTopicOf | wikipedia-en:Master_theorem_(analysis_of_algorithms) |
| is dbo:wikiPageDisambiguates of | dbr:Master_theorem |
| is dbo:wikiPageRedirects of | dbr:Master_Theorem dbr:Master's_Theorem dbr:Master_Method dbr:Master_method dbr:Mastor_theorem |
| is dbo:wikiPageWikiLink of | dbr:Quicksort dbr:Prune_and_search dbr:Binary_logarithm dbr:Analysis_of_algorithms dbr:Matrix_multiplication_algorithm dbr:Divide-and-conquer_algorithm dbr:Divide-and-conquer_eigenvalue_algorithm dbr:Hausdorff_dimension dbr:Akra–Bazzi_method dbr:Karatsuba_algorithm dbr:Kinetic_convex_hull dbr:Recurrence_relation dbr:Recursion_theorem dbr:James_B._Saxe dbr:Big_O_notation dbr:Dorothea_Blostein dbr:Merge_sort dbr:Ramer–Douglas–Peucker_algorithm dbr:Wolfgang_Haken dbr:Master_theorem dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:List_of_theorems dbr:Soft_heap dbr:X_+_Y_sorting dbr:Master_Theorem dbr:Master's_Theorem dbr:Master_Method dbr:Master_method dbr:Mastor_theorem |
| is foaf:primaryTopic of | wikipedia-en:Master_theorem_(analysis_of_algorithms) |
