The effectiveness of the traditional P-wave complexity in the discrimination between nuclear explosions and earthquakes is validated. Two improved algorithms of P-wave complexity in time domain are proposed and the recognition accuracy is increased a little. The traditional computation of complexity is generalized to time-frequency domain and a framework for the computation of complexity based on short time Fourier transform is given. Under the simplification form of the framework, seismic features are extracted based on Fisher methods. Classification results show that the proposed algorithm is better than other existing algorithms.