  Let $\mathrm{R}$ be a real closed field and $\mathrm{D} \subset \mathrm{R}$
an ordered domain. We give an algorithm that takes as input a polynomial $Q \in
\mathrm{D}[X_1,\ldots,X_k]$, and computes a description of a roadmap of the set
of zeros, $\mathrm{Zer}(Q,\mathrm{R}^k)$, of $Q$ in $\mathrm{R}^k$. The
complexity of the algorithm, measured by the number of arithmetic operations in
the ordered domain $\mathrm{D}$, is bounded by $d^{O(k \sqrt{k})}$, where $d =
\mathrm{deg}(Q)\ge 2$. As a consequence, there exist algorithms for computing
the number of semi-algebraically connected components of a real algebraic set,
$\mathrm{Zer}(Q,\mathrm{R}^k)$, whose complexity is also bounded by $d^{O(k
\sqrt{k})}$, where $d = \mathrm{deg}(Q)\ge 2$. The best previously known
algorithm for constructing a roadmap of a real algebraic subset of
$\mathrm{R}^k$ defined by a polynomial of degree $d$ has complexity
$d^{O(k^2)}$.
