Cycle detection using a stack |
| |
Authors: | Gabriel Nivasch |
| |
Affiliation: | Weizmann Institute of Science, Rehovot 76100, Israel |
| |
Abstract: | We present an algorithm for detecting periodicity in sequences produced by repeated application of a given function. Our algorithm uses logarithmic memory with high probability, runs in linear time, and is guaranteed to stop within the second loop through the cycle. We also present a partitioning technique that offers a time/memory tradeoff. Our algorithm is especially well suited for sequences where the cycle length is typically small compared to the length of the acyclic prefix. |
| |
Keywords: | Cycle detection Algorithms Analysis of algorithms Stack Time/memory tradeoff Random function |
本文献已被 ScienceDirect 等数据库收录! |