Problem size

Problem size

In the fields of algorithm analysis and computational complexity theory, the running time or space requirements of an algorithm are expressed as a function of the problem size. The problem size measures the size, in some sense, of the input to the algorithm. The problem size has to be cleanly defined before an algorithm analysis can be attempted.

For many problems, the problem size is taken to be the number of bits required to encode the input. For instance, if the problem is to square a given (nonzero) integer, we would typically measure the input size as one plus the floor of the base two logarithm of the input integer (since that describes how many bits are needed to encode the integer in binary notation). However, often the encoding of the input is not canonical; if for instance the problem is one in graph theory, then different problem sizes can be defined, since a graph can be encoded as a list of edges or alternatively as an adjacency matrix.


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • Size function — Size functions are shape descriptors, in a geometrical/topological sense. They are functions from the half plane to the natural numbers, counting certain connected components of a topological space. They are used in pattern recognition and… …   Wikipedia

  • Size-exclusion chromatography — Equipment for running size exclusion chromatography. The buffer is pumped through the column (right) by a computer controlled device Acronym SEC Classification Chromatography Analytes …   Wikipedia

  • Size changing — is the hypothetical process of reducing or enlarging the size, mass, and volume of an object in space, usually proportionally. It is a hypothetical process and is not to be confused with known processes where objects appear to change size through …   Wikipedia

  • Size of groups, organizations, and communities — Size (the number of people involved) is an important characteristic of the groups, organizations, and communities in which social behavior occurs. When only a few persons are interacting, adding just one more individual may make a big difference… …   Wikipedia

  • Problem of Apollonius — In Euclidean plane geometry, Apollonius problem is to construct circles that are tangent to three given circles in a plane (Figure 1); two circles are tangent if they touch at a single point. Apollonius of Perga (ca. 262 BC ndash; ca. 190 BC)… …   Wikipedia

  • Problem of universals — The problem of universals is an ancient problem in metaphysics about whether universals exist. Universals are general or abstract qualities, characteristics, properties, kinds or relations, such as being male/female, solid/liquid/gas or a certain …   Wikipedia

  • Problem of points — The problem of points, also called the problem of division of the stakes, is a classical problem in probability theory. One of the famous problems that motivated the beginnings of modern probability theory in the 17th century, it led Blaise… …   Wikipedia

  • Size exclusion chromatography — Infobox chemical analysis name = Size exclusion chromatography caption =Equipment for running size exclusion chromatography. The buffer is pumped through the column (right) by a computer controlled device acronym = SEC classification… …   Wikipedia

  • size — I. /saɪz / (say suyz) noun 1. the dimensions, proportions, or magnitude of anything: the size of a city; the size of a problem. 2. considerable or great magnitude: to seek size rather than quality. 3. one of a series of graduated measures for… …  

  • size up — verb to look at critically or searchingly, or in minute detail (Freq. 2) he scrutinized his likeness in the mirror • Syn: ↑take stock, ↑scrutinize, ↑scrutinise • Derivationally related forms: ↑scrutiniser ( …   Useful english dictionary

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”