To explore the correlation between the mutual information and complexity of nonlinear dynamic system, the nonlinear time series of Logistic map, Lorenz model and cardiac RR intervals were used as the experimental data. The multi-segmented time-delayed mutual information, multi-segmented Lempel-Ziv complexity and their correlation coefficients were calculated. The results show that the mutual information of these series are strongly negatively correlated with the complexity. For the 201 series generated by Logistic equation, the absolute value of all correlation coefficients between the mutual information and the complexity of various segments are 0.9126 plus and the maximum reach to 0.9923, and for the 94 series of cardiac RR intervals, they are 0.8555 plus and the maximum reach to 0.9860. The investigations also indicate that the mutual information is more sensitive than the complexity in characterizing a nonlinear dynamic system.