In computer science, a pointer algorithm (sometimes called a pointer machine, or a reference machine; see the article Pointer machine for a close but non-identical concept) is a type of algorithm that manages a linked data structure. This concept is used as a model for lower-bound proofs and specific restrictions on the linked data structure and on the algorithm's access to the structure vary.

This model has been used extensively with problems related to the disjoint-set data structure. Thus, Tarjan and La Poutré used this model to prove lower bounds on the amortized complexity of a disjoint-set data structure[1][2] (La Poutré also addressed the interval split-find problem). Blum used this model to prove a lower bound on the single operation worst-case time of disjoint set data structure.[3] Blum and Rochow proved a worst-case lower bound for the interval union-find problem.[4]

Example

edit

In Tarjan's lower bound for the disjoint set union problem, the assumptions on the algorithm are:

  • The algorithm maintains a linked structure of nodes.
  • Each element of the problem is associated with a node.
  • Each set is represented by a node.
  • The nodes of each set constitute a distinct connected component in the structure (this property is called separability).
  • The find operation is performed by following links from the element node to the set node.

Under these assumptions, the lower bound of on the cost of a sequence of m operations is proven.

References

edit
  1. ^ Tarjan, Robert E. (1979). "A class of algorithms which require nonlinear time to maintain disjoint sets". Journal of Computer and System Sciences. 18 (2): 110–127. doi:10.1016/0022-0000(79)90042-4.
  2. ^ La Poutré, Johannes A. (1990). "Lower bounds for the union-find and the split-find problem on pointer machines". Proceedings of the twenty-second annual ACM symposium on Theory of computing - STOC '90. ACM. pp. 34–44. doi:10.1145/100216.100221. ISBN 0-89791-361-2.
    • See also La Poutré, Han (1996). "Lower Bounds for the Union–Find and the Split–Find Problem on Pointer Machines". Journal of Computer and System Sciences. 52: 87–99. doi:10.1006/jcss.1996.0008.
  3. ^ Blum, Norbert (1986). "On the single operation worst-case time complexity of the disjoint set union problem". SIAM Journal on Computing. 15 (4): 1021–1024. doi:10.1137/0215072.
  4. ^ Blum, Norbert; Rochow, Henning (1994). "A lower bound on the single operation worst-case time complexity of the union-find problem on intervals". Information Processing Letters. 51 (2): 57–60. doi:10.1016/0020-0190(94)00082-4.

📚 Artikel Terkait di Wikipedia

In-place algorithm

strictest form, the algorithm can only have a constant amount of extra space, counting everything including function calls and pointers. However, this form

Cycle detection

Several algorithms are known for finding cycles quickly and with little memory. Robert W. Floyd's tortoise and hare algorithm moves two pointers at different

Level ancestor problem

time. The jump pointer algorithm associates up to log n pointers to each vertex of the tree. These pointers are called jump pointers because they jump

Pointer machine

a pointer machine is an atomistic abstract computational machine whose storage structure is a graph. A pointer algorithm could also be an algorithm restricted

Cheney's algorithm

moving the scanning pointer over them. When the scanning pointer reaches the free-space pointer, the gray set is empty, and the algorithm ends. Cheney, C

Pointer (computer programming)

in a calculation. Because indirection is a fundamental aspect of algorithms, pointers are often expressed as a fundamental data type in programming languages;

LZ77 and LZ78

LZ77 and LZ78 are the two lossless data compression algorithms published in papers by Abraham Lempel and Jacob Ziv in 1977 and 1978. They are also known

Disjoint-set data structure

that this was the lower bound for a certain class of algorithms, pointer algorithms, that include the Galler-Fischer structure. In 1989, Fredman and Saks