Metadata
Author: WikiMatrix
Data
English[en]
For example, if (a) the base cases have constant-bounded size, the work of splitting the problem and combining the partial solutions is proportional to the problem's size n, and (b) there is a bounded number p of subproblems of size ~ n/p at each stage, then the cost of the divide-and-conquer algorithm will be O(n logpn).
Galician[gl]
Por exemplo, se o traballo de dividir o problema e de combinar as solucións parciais é proporcional ao tamaño do problema (n); ademais, hai un número limitado p de subproblemas de tamaño aproximadamente igual a n/p en cada etapa; e para rematar, os casos basee requiren un tempo constante (Ou(1)); entón o algoritmo divide e vencerás ten por cota superior asintótica a Ou(nlogn).