Divide-and-conquer algorithm
In computer science, divide and conquer is an algorithm design paradigm. A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.
- Comment
- enIn computer science, divide and conquer is an algorithm design paradigm. A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.
- Depiction
- Has abstract
- enIn computer science, divide and conquer is an algorithm design paradigm. A divide-and-conquer algorithm recursively breaks down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem. The divide-and-conquer technique is the basis of efficient algorithms for many problems, such as sorting (e.g., quicksort, merge sort), multiplying large numbers (e.g., the Karatsuba algorithm), finding the closest pair of points, syntactic analysis (e.g., top-down parsers), and computing the discrete Fourier transform (FFT). Designing efficient divide-and-conquer algorithms can be difficult. As in mathematical induction, it is often necessary to generalize the problem to make it amenable to a recursive solution. The correctness of a divide-and-conquer algorithm is usually proved by mathematical induction, and its computational cost is often determined by solving recurrence relations.
- Is primary topic of
- Divide-and-conquer algorithm
- Label
- enDivide-and-conquer algorithm
- Link from a Wikipage to another Wikipage
- Akra–Bazzi method
- Algorithm
- Algorithm design paradigm
- Analysis of algorithms
- Anatolii Alexeevitch Karatsuba
- Andrey Kolmogorov
- Arm's-length recursion
- Asymptotic complexity
- Babylonia
- Big O notation
- Binary search
- Bisection algorithm
- Bottom-up design
- Branch-and-bound
- Breadth first recursion
- Cache-oblivious algorithm
- Call stack
- Carl Friedrich Gauss
- Category:Algorithms
- Category:Divide-and-conquer algorithms
- Category:Optimization algorithms and methods
- Chart parsing
- Closest pair of points problem
- Computer science
- Conditional (programming)
- Cooley–Tukey FFT algorithm
- Decomposable aggregation function
- Discrete Fourier transform
- Donald Knuth
- Dynamic programming
- Euclidean algorithm
- Fast Fourier transform
- File:Merge sort algorithm diagram.svg
- Floating-point
- Fork–join model
- Geometric series
- Greatest common divisor
- Heuristic (computer science)
- Hybrid algorithm
- IBM 80 series Card Sorters
- Insertion sort
- John Mauchly
- John von Neumann
- Karatsuba algorithm
- Loop (computing)
- Loop nest optimization
- Loop unwinding
- MapReduce
- Master theorem (analysis of algorithms)
- Mathematical induction
- Memoization
- Memory cache
- Merge sort
- Multiplication algorithm
- Non-uniform memory access
- Numerical algorithm
- Pairwise summation
- Partial evaluation
- Post office
- Priority queue
- Prune and search
- Queue (data structure)
- Quicksort
- Radix sort
- Recurrence relation
- Recursion (computer science)
- Root-finding algorithm
- Shared-memory
- Sorting algorithm
- Source-code generation
- Stack (data structure)
- Stack overflow
- Strassen algorithm
- Syntactic analysis
- Tail recursion
- Top-down parser
- Tower of Hanoi
- Virtual memory
- SameAs
- 4291466-8
- 4qq8g
- Agoritmo divide e vencerás
- Algorisme divideix i venceràs
- Algoritmo divide y vencerás
- Deili- og drottnunarreiknirit
- Deli in vladaj (računalništvo)
- Divide and Conquer
- Divide and conquer algorithm
- Divide et impera (informatica)
- Divide et impera (informatică)
- Divide et impera (informatika)
- Divisão e conquista
- Diviser pour régner (informatique)
- Dziel i zwyciężaj
- Jaga-ja-valitse algoritm
- Parçala və idarə et (alqoritm)
- Q671298
- Rozděl a panuj (algoritmus)
- Splitt og hersk-algoritme
- Teile-und-herrsche-Verfahren
- Thuật toán chia để trị
- Zatitu eta irabazi erako algoritmo
- Διαίρει και βασίλευε (υπολογιστές)
- Подели па владај (информатика)
- Разделяй и властвуй (информатика)
- Розділяй та володарюй (інформатика)
- אלגוריתם הפרד ומשול
- الگوریتم تقسیم و حل
- خوارزمية فرق تسد
- बाँटो-और-जीतो कलनविधि
- ขั้นตอนวิธีแบ่งแยกและเอาชนะ
- 分割統治法
- 分治法
- 분할 정복 알고리즘
- Subject
- Category:Algorithms
- Category:Divide-and-conquer algorithms
- Category:Optimization algorithms and methods
- Thumbnail
- WasDerivedFrom
- Divide-and-conquer algorithm?oldid=1123297957&ns=0
- WikiPageLength
- 19431
- Wikipage page ID
- 201154
- Wikipage revision ID
- 1123297957
- WikiPageUsesTemplate
- Template:Algorithmic paradigms
- Template:Authority control
- Template:Commons category
- Template:Examples
- Template:Reflist
- Template:Short description
