The complexity series of the Guliya (Tibetan plateau) ice core and Shihua cave (Beijing) stalagmite proxy records were respectively calculated in this paper, using a dynamical nonlinear analysis method for time series-Lemper-Ziv complexityalgorithm; and the physical implication of Lemper-Ziv complexity and its meaning in the study of climate change were also discussed. The wavelet analysis resul ts show that there exist distinctive quasi-periods of 780_, 380_, 160_, and 105_ year in the complexity series. Further investigations indicate that when differ ent window lengths are selected, the characters of the complexity series for a g iven time series are basically the same, and there exists the coherency between the jumps of the complexity series and the climatic jumps on various timescales . This paper presents, for the first time so far as we know, the oscillation on 380_year timescale in the recent millennium, with amplitude decaying and intri nsic period reducing. The complexity of the time series has gradually reduced si nce 1900. For the complexity of the stalagmite data,there has been the quasi-equ al-amplitude oscillation after 1920, which is similar to the circumstances of th e warming epochs over China in the middle of the sixth century and the middle o f the twelfth century. Consequently, the reason for the warming in the twentiet h century remains to be necessary to study.