I was wondering if there are any known (upper and lower) bounds for the complexity of computing the class-number of a finite extension of the rationals. (A general bound should be in function of the discriminant, I guess.)

This would also be of interest in special cases like fields with a given degree or signature. The simplest one would be the family of imaginary quadratic fields: in this setting there is Swan's algorithm (which actually computes reduced bases for all ideals of least norms in their class), which takes (I think) at most $m^3$ steps to do $\mathbb{Q}(\sqrt{-m})$ when implemented without more thought. Is there a better algorithm known, or is there a speedy implementation of Swan's algorithm?