In computer science (specifically computational complexity theory), the worst-case complexity measures the resources (e.g. running time, memory) that an algorithm requires given an input of arbitrary size (commonly denoted as n in asymptotic notation). It gives an upper bound on the resources required by the algorithm. The worst-case complexity of an algorithm should be contrasted with its average-case complexity, which is an average measure of the amount of resources the algorithm uses on a random input.
Attributes | Values |
---|
rdfs:label
| - Complexité dans le pire des cas (fr)
- Complexidade de pior caso (pt)
- Worst-case complexity (en)
- Найгірший випадок складності (uk)
|
rdfs:comment
| - En informatique, la complexité dans le pire des cas, ou complexité dans le cas le plus défavorable, mesure la complexité (par exemple en temps ou en espace) d'un algorithme dans le pire des cas d'exécution possibles. Elle est exprimée comme une fonction de la taille de l'entrée de l'algorithme. Implicitement, on cherche à construire des algorithmes s'exécutant en utilisant le moins de ressources possible (e.g. le plus vite possible), et il s'agit par conséquent d'une borne supérieure des ressources requises par l'algorithme. (fr)
- In computer science (specifically computational complexity theory), the worst-case complexity measures the resources (e.g. running time, memory) that an algorithm requires given an input of arbitrary size (commonly denoted as n in asymptotic notation). It gives an upper bound on the resources required by the algorithm. The worst-case complexity of an algorithm should be contrasted with its average-case complexity, which is an average measure of the amount of resources the algorithm uses on a random input. (en)
- Na Ciência da computação a “Complexidade de pior caso” (usualmente denotada em notação assintótica) mede os recursos (ex. tempo de execução, memória) que um algoritmo precisa no pior caso. Isto dá um limitante superior dos recursos necessários ao algoritmo. No caso de tempo de execução, a complexidade de pior caso indica o maior tempo de execução de um algoritmo dado “qualquer" entrada de tamanho “n”, e assim isto garante que o algoritmo termine no tempo. Além disso, a ordem de crescimento da complexidade de pior caso é usado para comparar a eficiência de dois algoritmos. (pt)
|
dcterms:subject
| |
Wikipage page ID
| |
Wikipage revision ID
| |
Link from a Wikipage to another Wikipage
| |
sameAs
| |
dbp:wikiPageUsesTemplate
| |
has abstract
| - En informatique, la complexité dans le pire des cas, ou complexité dans le cas le plus défavorable, mesure la complexité (par exemple en temps ou en espace) d'un algorithme dans le pire des cas d'exécution possibles. Elle est exprimée comme une fonction de la taille de l'entrée de l'algorithme. Implicitement, on cherche à construire des algorithmes s'exécutant en utilisant le moins de ressources possible (e.g. le plus vite possible), et il s'agit par conséquent d'une borne supérieure des ressources requises par l'algorithme. Par exemple, la complexité en temps dans le pire des cas correspond au temps d'exécution le plus long que puisse avoir l'algorithme, et permet d'en garantir la terminaison. La complexité dans le pire des cas permet de comparer l'efficacité de deux algorithmes. Elle s'oppose à la complexité en moyenne. (fr)
- In computer science (specifically computational complexity theory), the worst-case complexity measures the resources (e.g. running time, memory) that an algorithm requires given an input of arbitrary size (commonly denoted as n in asymptotic notation). It gives an upper bound on the resources required by the algorithm. In the case of running time, the worst-case time complexity indicates the longest running time performed by an algorithm given any input of size n, and thus guarantees that the algorithm will finish in the indicated period of time. The order of growth (e.g. linear, logarithmic) of the worst-case complexity is commonly used to compare the efficiency of two algorithms. The worst-case complexity of an algorithm should be contrasted with its average-case complexity, which is an average measure of the amount of resources the algorithm uses on a random input. (en)
- Na Ciência da computação a “Complexidade de pior caso” (usualmente denotada em notação assintótica) mede os recursos (ex. tempo de execução, memória) que um algoritmo precisa no pior caso. Isto dá um limitante superior dos recursos necessários ao algoritmo. No caso de tempo de execução, a complexidade de pior caso indica o maior tempo de execução de um algoritmo dado “qualquer" entrada de tamanho “n”, e assim isto garante que o algoritmo termine no tempo. Além disso, a ordem de crescimento da complexidade de pior caso é usado para comparar a eficiência de dois algoritmos. A complexidade de pior tempo de um algoritmo deve ser contratada com o seu complexidade de caso médio, que é uma medida média da quantidade de recursos que o algoritmo usa numa entrada aleatória (pt)
|
prov:wasDerivedFrom
| |
page length (characters) of wiki page
| |
foaf:isPrimaryTopicOf
| |
is rdfs:seeAlso
of | |
is Link from a Wikipage to another Wikipage
of | |
is Wikipage redirect
of | |
is foaf:primaryTopic
of | |