Metraipolis › archive › dc_0894350bb6fa

Divide-and-conquer algorithm — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Divide-and-conquer_algorithm
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-06T16:45:20.440Z
SHA-256 of the archived text
607aae3d3cda9dbe9f87d316a8ad5e48786d08c44b8a9545395fadfc118c8083
Stable URL of this page
https://metraipolis.com/documento/dc_0894350bb6fa

How to cite

Divide-and-conquer algorithm — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Divide-and-conquer_algorithm (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_0894350bb6fa (Metraipolis archive dc_0894350bb6fa, sha256 607aae3d3cda9dbe9f87d316a8ad5e48786d08c44b8a9545395fadfc118c8083)
BibTeX
@misc{dc0894350bb6fa,
  title = {Divide-and-conquer algorithm — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Divide-and-conquer_algorithm},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_0894350bb6fa; sha256 607aae3d3cda9dbe9f87d316a8ad5e48786d08c44b8a9545395fadfc118c8083},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Divide-and-conquer_algorithm. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

In computer science, divide and conquer, originally a political maxim, designates 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), SAT solving, 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.

Tema degli esploratori: statistica e scienza dei dati (deposito sistematico; categoria «Algorithms»).
Fonte: Wikipedia in inglese, voce «Divide-and-conquer algorithm» — https://en.wikipedia.org/wiki/Divide-and-conquer_algorithm
Wikidata Q671298 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q671298
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Divide-and-conquer_algorithm?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1363143428, consultata il 2026-10-06T15:18:53.068Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: c051f877c7b7b96d1a2cbb052e2c85961bdf3f0420454ad6fc1332de1e8ac1fd