﻿ Algorithms and Data Structures Glossary (Starting with "Q")
 Home Free Glossaries Free Dictionaries Post Your Translation Job! Free Articles Jobs for Translators

#### Algorithms and Data Structures Glossary(Starting with "Q")

By www.nist.gov,
Gaithersburg, Maryland, U.S.A.

paul . black [at] nist . gov

Use the search bar to look for terms in all glossaries, dictionaries, articles and other resources simultaneously

 A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

### Q

qm sort
q sort
quantum computation
queue
quick search
quicksort

(algorithm)

Definition: A method of open addressing for a hash table in which a collision is resolved by putting the item in the next empty place given by a probe sequence. The space between places in the sequence increases quadratically.

Note: Deletion may be hard because finding collisions again relies on not creating empty spots. One solution is to mark an entry as deleted so it can be reused for insertion, but the search list is intact.

Author: PEB

An explanation of how quadratic equations got their name.

(data structure)

Definition: A tree where each node is split along all d dimensions, leading to 2d children.

Note: It was originally designed for 2-dimensional data (pictures), so each node had four children, hence quadtree. After [GG98].

Author: PEB

(definition)

Definition: The number of nodes in a quadtree region representation for a simple polygon (i.e. with nonintersecting edges and without holes) is O(p+q) for a 2q× 2q image with perimeter p measured in pixel widths. In most cases, q is negligible, and thus, the number of nodes is proportional to the perimeter. It also holds for three-dimensional data where the perimeter is replaced by surface area, and in general for d-dimensions where instead of perimeter we have the size of the (d-1)-dimensional interfaces between the d-dimensional objects.

Note: From Algorithms and Theory of Computation Handbook, page 18-24, Copyright © 1999 by CRC Press LLC. Appearing in the Dictionary of Computer Science, Engineering and Technology, Copyright © 2000 CRC Press LLC.

Author: CRC-A

(data structure)

Definition: A tree in which each node is split according to some subset of the key, typically a character.

Note: After [GBY91, pages 146-149].

The name comes from reTRIEval and is pronounced, "tree." See the historical note at trie.

Author: PEB

#### quantum computation

(definition)

Definition: Computation based on quantum mechanical effects, such as superposition and entanglement, in addition to classical digital manipulations.

Specialization (... is a kind of me.)
Shor's algorithm, Grover's algorithm, Simon's algorithm, Deutsch-Jozsa algorithm.

Note: Quantum computers can, in theory, make computations that are impossible to do exactly with classical computers or achieve exponential speedup. Since nobody has yet (as of February 2005) implemented more than a few bit operations, problems such as decoherence and measurement error may limit quantum computation to a few specialized roles.

Author: PEB

Ethan Bernstein and Umesh Vazirani, Quantum Complexity Theory, SIAM Journal on Computing, 26(5):1411-1473, 1997.

#### queue

(data structure)

Definition: A collection of items in which only the earliest added item may be accessed. Basic operations are add (to the tail) or enqueue and delete (from the head) or dequeue. Delete returns the item removed. Also known as "first-in, first-out" or FIFO.

Formal Definition: It is convenient to define delete or dequeue in terms of remove and a new operation, front. The operations new(), add(v, Q), front(Q), and remove(Q) may be defined with axiomatic semantics as follows.

1. new() returns a queue
where Q is a queue and v and w are values.

Also known as FIFO.

Generalization (I am a kind of ...)
abstract data type.

Specialization (... is a kind of me.)
bounded queue.

Author: PEB

Demonstrations with dynamic array, fixed array, and linked list implementations.

#### quick search

(algorithm)

Definition: A string matching algorithm that compares characters from the end of the search string to its beginning. When a character doesn't match, the next character in the text beyond the search string determines where the next possible match begins.

Note: After [Sund98].

Author: PEB

#### quicksort

(algorithm)

Definition: Pick an element from the array (the pivot), partition the remaining elements into those greater than and less than this pivot, and recursively sort the partitions. There are many variants of the basic scheme above: to select the pivot, to partition the array, to stop the recursion on small partitions, etc.

Generalization (I am a kind of ...)
in-place sort.

Specialization (... is a kind of me.)
balanced quicksort, multikey Quicksort, introspective sort.

Aggregate child (... is a part of or used in me.)
partition, divide and conquer, recursion, Select, sublinear time algorithm.

Note: Quicksort has running time Θ(n²) in the worst case, but it is typically O(n log n). In practical situations, a finely tuned implementation of quicksort beats most sort algorithms, including sort algorithms whose theoretical complexity is O(n log n) in the worst case.

Select can be used to always pick good pivots, thus giving a variant with O(n log n) worst-case running time.

Author: CM

Java applet animation (Java). Comparison of quicksort, heapsort, and merge sort on modern processors.

 A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z

Published - April 2009

Find free glossaries at TranslationDirectory.com

Find free dictionaries at TranslationDirectory.com

Translation agencies are welcome to register here - Free!

Freelance translators are welcome to register here - Free!

Submit your glossary or dictionary for publishing at TranslationDirectory.com