Editing Algorithm (section)

=== By design paradigm ===
Another way of classifying algorithms is by their design methodology or [[algorithmic paradigm|paradigm]]. Some common paradigms are:

; [[Brute-force search|Brute-force]] or exhaustive search
: Brute force is a problem-solving method of systematically trying every possible option until the optimal solution is found. This approach can be very time-consuming, testing every possible combination of variables. It is often used when other methods are unavailable or too complex. Brute force can solve a variety of problems, including finding the shortest path between two points and cracking passwords.
; Divide and conquer
: A [[divide-and-conquer algorithm]] repeatedly reduces a problem to one or more smaller instances of itself (usually [[recursion|recursively]]) until the instances are small enough to solve easily. [[mergesort|Merge sorting]] is an example of divide and conquer, where an unordered list is repeatedly split into smaller lists, which are sorted in the same way and then merged.<ref>{{cite book|title=Algorithm Design: Foundations, Analysis, and Internet Examples|first1=Michael T.|last1=Goodrich|first2=Roberto|last2=Tamassia|publisher=John Wiley & Sons|year=2001|isbn=9780471383659|contribution=5.2 Divide and Conquer|page=263}}</ref> In a simpler variant of divide and conquer called [[prune and search]] or ''decrease-and-conquer algorithm'', which solves one smaller instance of itself, and does not require a merge step.{{sfnp|Goodrich|Tamassia|2001|loc=4.7.1 Prune-and-search|p=245}} An example of a prune and search algorithm is the [[binary search algorithm]].
; Search and enumeration
: Many problems (such as playing [[Chess|ches]]s) can be modelled as problems on [[graph theory|graph]]s. A [[graph exploration algorithm]] specifies rules for moving around a graph and is useful for such problems. This category also includes [[search algorithm]]s, [[branch and bound]] enumeration, and [[backtracking]].
;[[Randomized algorithm]]
: Such algorithms make some choices randomly (or pseudo-randomly). They find approximate solutions when finding exact solutions may be impractical (see heuristic method below). For some problems, the fastest approximations must involve some [[randomness]].<ref>For instance, the [[volume]] of a [[convex polytope]] (described using a membership oracle) can be approximated to high accuracy by a randomized polynomial time algorithm, but not by a deterministic one: see {{cite journal
 | last1 = Dyer | first1 = Martin
 | last2 = Frieze | first2 = Alan
 | last3 = Kannan | first3 = Ravi
 | date = January 1991
 | doi = 10.1145/102782.102783
 | issue = 1
 | journal = J. ACM
 | pages = 1–17
 | title = A Random Polynomial-time Algorithm for Approximating the Volume of Convex Bodies
 | volume = 38| citeseerx = 10.1.1.145.4600| s2cid = 13268711
 }}</ref> Whether randomized algorithms with [[P (complexity)|polynomial time complexity]] can be the fastest algorithm for some problems is an open question known as the [[P versus NP problem]]. There are two large classes of such algorithms:
# [[Monte Carlo algorithm]]s return a correct answer with high probability. E.g. [[RP (complexity)|RP]] is the subclass of these that run in [[polynomial time]].
# [[Las Vegas algorithm]]s always return the correct answer, but their running time is only probabilistically bound, e.g. [[Zero-error Probabilistic Polynomial time|ZPP]].
; [[Reduction (complexity)|Reduction of complexity]]
: This technique transforms difficult problems into better-known problems solvable with (hopefully) [[asymptotically optimal]] algorithms. The goal is to find a reducing algorithm whose [[Computational complexity theory|complexity]] is not dominated by the resulting reduced algorithms. For example, one [[selection algorithm]] finds the median of an unsorted list by first sorting the list (the expensive portion), and then pulling out the middle element in the sorted list (the cheap portion). This technique is also known as ''[[Transform and conquer algorithm|transform and conquer]]''.
; [[Back tracking]]
: In this approach, multiple solutions are built incrementally and abandoned when it is determined that they cannot lead to a valid full solution.