As commented by the two answers, Pollard Rho is the best known algorithm for discrete logarithms in a generic cyclic group (where no other special structure is used, and no such special structure, e.g., amenability to index calculus).

The so called *baby step giant step* algorithm can also be used with essentially the same time complexity $O(\sqrt{n})$ where $|G|=n,$ as Pollard Rho. Unfortunately the bsgs needs memory of the same order as well, while Pollard Rho requires negligible memory.

So, if $p$ has size $b$ bits, the time complexity for both Pollard Rho and bsgs is $O(2^{b/2}),$ and thus still exponential in input size $b.$ The bsgs is based on a very neat idea, see below:

**Input:** $x=g^k,$ where $g$ is a generator of a multiplicative cyclic group of size $n$, say $\mathbb{Z}_p^\ast$ for simplicity. The goal is to recover $k,$ and $g$ is public as well as $p$ and the group operation. Let $m=\lceil \sqrt{n}~\rceil.$

**Step 1. Precomputation:** Form the list $$L=\{(j,g^{jm}):j=0,1,\ldots,m-1\}$$ and store it sorted on the second component (or you could use a hash table and a lookup to find an entry in step 2 below). *Complexity:* $O(\sqrt{n}\log n)$ time (with hash sorting time complexity would be $O(\sqrt{n})$ but generally additional memory is needed to control collisions in that case) and $O(\sqrt{n})$ memory.

Think of the elements of $G$ in a $\lceil m\rceil \times \lceil m \rceil$ array (with some repeats at the end):
$$
\begin{array}{cccccc}
1 & g & g^2 & g^3 &\cdots & g^{m-1} \\
g^m & g^{m+1} & g^{m+2} & g^{m+3} & \cdots & g^{2m-1} \\
\vdots & & & & \vdots\\
g^{m(m-1)} & g^{m(m-1)+1} & \cdots & g^{n-1} & 1 & \cdots\\
\end{array}
$$

**Step 2. Online Phase** Note that the list $L$ has the entries in the first column *sorted as integers*.
Now, form the elements $x,xg,\ldots, xg^i,\ldots,$ sequentially and lookup in $L$ until the element is found in $L$ (clearly this is guaranteed, as long as we continue until $xg^{m-1}$, since this operation spans two consecutive rows of the array starting at $x$ and ending at $x g^m$ which is below $x$ and one position to the left).

When we find an element in $L,$ at the $i_0$th iteration of Step 2, we then know
$$
xg^{i_0-1}=g^{j_0m}
$$
where $i_0,j_0$ are known. Solving we get $x=g^{j_0 m-i_0+1}$ so $k=j_0 m-i_0+1\pmod n.$

Note that if you have a new $x,$ you can just repeat Step 2.

One final comment which may be of interest. About 6 years ago there was quite a lot of progress in the DLP algorithms for composite order fields with special exponents (I am quoting a cryptography stack exchange question here below):

A recent paper by Göloğlu, Granger, McGuire, and Zumbrägel: Solving a 6120-bit DLP on a Desktop Computer seems to "demonstrate a practical DLP break in the finite field of $2^{6120}$ elements, using just a single core-month". They credit a 2012 paper by Antoine Joux: Faster index calculus for the medium prime case. Application to 1175-bit and 1425-bit finite field for paving the way they explore. In 2013 Joux published A new index calculus algorithm with complexity $L(1/4+o(1))$ in very small characteristic, and very recently announced he "is able to compute discrete logarithms in $GF(2^{6168})=GF({(2^{257})}^{24})$ using less than 550 CPU.hours".

This puts some pairing-based cryptographic schemes relying on the hardness of DLP in fields of characteristic 2 at risk, but not prime field based schemes, be it classical integer residue field DLP or elliptic curve DLP.