Faster access than browser!
30 relations: Abstract machine, Analysis of algorithms, Big O notation, Binary number, Binary search algorithm, Cache-oblivious algorithm, Chan's algorithm, Comparison sort, Complexity class, Computational complexity theory, Computational number theory, Convex hull, Cryptography, EXPTIME, Graph (discrete mathematics), Insertion sort, List of algorithms, Multiplication algorithm, NP (complexity), NP-completeness, Oracle machine, Output-sensitive algorithm, P (complexity), P-complete, Primality test, Radix sort, Random-access machine, Trial division, Turing machine, Unary coding.
Abstract machine
An abstract machine, also called an abstract computer, is a theoretical model of a computer hardware or software system used in automata theory.
New!!: Context of computational complexity and Abstract machine · See more »
Analysis of algorithms
In computer science, the analysis of algorithms is the determination of the computational complexity of algorithms, that is the amount of time, storage and/or other resources necessary to execute them.
New!!: Context of computational complexity and Analysis of algorithms · See more »
Big O notation
Big O notation is a mathematical notation that describes the limiting behaviour of a function when the argument tends towards a particular value or infinity.
New!!: Context of computational complexity and Big O notation · See more »
Binary number
In mathematics and digital electronics, a binary number is a number expressed in the base-2 numeral system or binary numeral system, which uses only two symbols: typically 0 (zero) and 1 (one).
New!!: Context of computational complexity and Binary number · See more »
Binary search algorithm
In computer science, binary search, also known as half-interval search,logarithmic search, or binary chop, is a search algorithm that finds the position of a target value within a sorted array.
New!!: Context of computational complexity and Binary search algorithm · See more »
Cache-oblivious algorithm
In computing, a cache-oblivious algorithm (or cache-transcendent algorithm) is an algorithm designed to take advantage of a CPU cache without having the size of the cache (or the length of the cache lines, etc.) as an explicit parameter.
New!!: Context of computational complexity and Cache-oblivious algorithm · See more »
Chan's algorithm
In computational geometry, Chan's algorithm, named after Timothy M. Chan, is an optimal output-sensitive algorithm to compute the convex hull of a set P of n points, in 2- or 3-dimensional space.
New!!: Context of computational complexity and Chan's algorithm · See more »
Comparison sort
A comparison sort is a type of sorting algorithm that only reads the list elements through a single abstract comparison operation (often a "less than or equal to" operator or a three-way comparison) that determines which of two elements should occur first in the final sorted list.
New!!: Context of computational complexity and Comparison sort · See more »
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity.
New!!: Context of computational complexity and Complexity class · See more »
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other.
New!!: Context of computational complexity and Computational complexity theory · See more »
Computational number theory
In mathematics and computer science, computational number theory, also known as algorithmic number theory, is the study of algorithms for performing number theoretic computations.
New!!: Context of computational complexity and Computational number theory · See more »
Convex hull
In mathematics, the convex hull or convex envelope or convex closure of a set X of points in the Euclidean plane or in a Euclidean space (or, more generally, in an affine space over the reals) is the smallest convex set that contains X. For instance, when X is a bounded subset of the plane, the convex hull may be visualized as the shape enclosed by a rubber band stretched around X., p. 3.
New!!: Context of computational complexity and Convex hull · See more »
Cryptography
Cryptography or cryptology (from κρυπτός|translit.
New!!: Context of computational complexity and Cryptography · See more »
EXPTIME
In computational complexity theory, the complexity class EXPTIME (sometimes called EXP or DEXPTIME) is the set of all decision problems that have exponential runtime, i.e., that are solvable by a deterministic Turing machine in O(2p(n)) time, where p(n) is a polynomial function of n. In terms of DTIME, We know and also, by the time hierarchy theorem and the space hierarchy theorem, that so at least one of the first three inclusions and at least one of the last three inclusions must be proper, but it is not known which ones are.
New!!: Context of computational complexity and EXPTIME · See more »
Graph (discrete mathematics)
In mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related".
New!!: Context of computational complexity and Graph (discrete mathematics) · See more »
Insertion sort
Insertion sort is a simple sorting algorithm that builds the final sorted array (or list) one item at a time.
New!!: Context of computational complexity and Insertion sort · See more »
List of algorithms
The following is a list of algorithms along with one-line descriptions for each.
New!!: Context of computational complexity and List of algorithms · See more »
Multiplication algorithm
A multiplication algorithm is an algorithm (or method) to multiply two numbers.
New!!: Context of computational complexity and Multiplication algorithm · See more »
NP (complexity)
In computational complexity theory, NP (for nondeterministic polynomial time) is a complexity class used to describe certain types of decision problems.
New!!: Context of computational complexity and NP (complexity) · See more »
NP-completeness
In computational complexity theory, an NP-complete decision problem is one belonging to both the NP and the NP-hard complexity classes.
New!!: Context of computational complexity and NP-completeness · See more »
Oracle machine
In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems.
New!!: Context of computational complexity and Oracle machine · See more »
Output-sensitive algorithm
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.
New!!: Context of computational complexity and Output-sensitive algorithm · See more »
P (complexity)
In computational complexity theory, P, also known as PTIME or DTIME(nO(1)), is a fundamental complexity class.
New!!: Context of computational complexity and P (complexity) · See more »
P-complete
In complexity theory, a decision problem is P-complete (complete for the complexity class '''P''') if it is in P and every problem in P can be reduced to it by an appropriate reduction.
New!!: Context of computational complexity and P-complete · See more »
Primality test
A primality test is an algorithm for determining whether an input number is prime.
New!!: Context of computational complexity and Primality test · See more »
Radix sort
In computer science, radix sort is a non-comparative integer sorting algorithm that sorts data with integer keys by grouping keys by the individual digits which share the same significant position and value.
New!!: Context of computational complexity and Radix sort · See more »
Random-access machine
In computer science, random-access machine (RAM) is an abstract machine in the general class of register machines.
New!!: Context of computational complexity and Random-access machine · See more »
Trial division
Trial division is the most laborious but easiest to understand of the integer factorization algorithms.
New!!: Context of computational complexity and Trial division · See more »
Turing machine
A Turing machine is a mathematical model of computation that defines an abstract machine, which manipulates symbols on a strip of tape according to a table of rules.
New!!: Context of computational complexity and Turing machine · See more »
Unary coding
Unary coding, sometimes called thermometer code, is an entropy encoding that represents a natural number, n, with n ones followed by a zero (if natural number is understood as non-negative integer) or with n − 1 ones followed by a zero (if natural number is understood as strictly positive integer).
New!!: Context of computational complexity and Unary coding · See more »
Redirects here:
Bit complexity, Complexity of computation (bit).
References
[1] https://en.wikipedia.org/wiki/Context_of_computational_complexity
