In the case of quadratic fields there is a very nice paper of Andy Booker (see http://www.ams.org/journals/mcom/2006-75-255/S0025-5718-06-01850-3/home.html ) which uses the Burgess bounds on character sums (among other ideas) to compute the class number. The running time is always $O(D^{1/2+\epsilon})$ and if the GRH is true then the algorithm executes in time $O(D^{1/4+\epsilon})$. I think this is the best that is known. If one wants all class numbers up to a point then there are other clever algorithms based on the trace formula for doing this (see work of Jacobson, Ramachandran and Williams; Springer Lecture notes in CS vol 4076).

In the case of quadratic fields there is a very nice paper of Andy Booker (see http://www.ams.org/journals/mcom/2006-75-255/S0025-5718-06-01850-3/home.html ) which uses the Burgess bounds on character sums (among other ideas) to compute the class number. The running time is always $O(D^{1/2+\epsilon})$ and if the GRH is true then the algorithm executes in time $O(D^{1/4+\epsilon})$. I think this is the best that is known. If one wants all class numbers up to a point then there are other clever algorithms based on the trace formula for doing this (see work of Jacobson, Ramachandran and Williams; Springer Lecture notes in CS vol 4076).

Note: As Edgardo observes there are faster randomized algorithms, and also earlier algorithms that rely on GRH (either running in heuristically subexponential time, or in time $D^{1/4+\epsilon}$). But these use GRH in an essential way in that the algorithm halts only if GRH is true. A subtle difference in Booker's algorithm is that it is guaranteed to halt; only the analysis of how long it takes to halt depends on GRH.