Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Output-sensitive algorithm
Résumé
In computer science, an output-sensitive algorithm is an algorithm whose running time depends on the size of the output, instead of, or in addition to, the size of the input. For certain problems where the output size varies widely, for example from linear in the size of the input to quadratic in the size of the input, analyses that take the output size explicitly into account can produce better runtime bounds that differentiate algorithms that would otherwise have identical asymptotic complexity.
A simple example of an output-sensitive algorithm is given by the division algorithm division by subtraction which computes the quotient and remainder of dividing two positive integers using only addition, subtraction, and comparisons:
def divide(number: int, divisor: int) -> Tuple[int, int]:
"""Division by subtraction."""
if divisor == 0:
raise ZeroDivisionError
if number < 1 or divisor < 1:
raise ValueError(
f"Positive integers only for "
f"dividend ({number}) and divisor ({divisor})."
)
q = 0
r = number
while r >= divisor:
q += 1
r -= divisor
return q, r
Example output:
divide(10, 2) (5, 0) divide(10, 3) (3, 1) This algorithm takes Θ(Q) time, and so can be fast in scenarios where the quotient Q is known to be small. In cases where Q is large however, it is outperformed by more complex algorithms such as long division. Convex hull algorithms for finding the convex hull of a finite set of points in the plane require Ω(n log n) time for n points; even relatively simple algorithms like the Graham scan achieve this lower bound. If the convex hull uses all n points, this is the best we can do; however, for many practical sets of points, and in particular for random sets of points, the number of points h in the convex hull is typically much smaller than n. Consequently, output-sensitive algorithms such as the ultimate convex hull algorithm and Chan's algorithm which require only O(n log h) time are considerably faster for such point sets.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.