Understanding the complexity of natural systems, such as climate systems, is critical for various research purposes and applications. The paper proposes an improved Grassberger-Procaccia (G-P) algorithm, which integrates the normal-based K-means clustering technique and Random Sample Consensus algorithm (RANSAC) for computing correlation dimensions. The results revealed that the new method outperformed traditional algorithms in computing correlation dimensions for both chaotic systems. Based on the new algorithm, the complexity of precipitation and air temperature in the Haihe River basin (HRB) in northeast China was further evaluated. The results showed that considerable regional differences exist in the complexity of both climatic variables across the HRB. Specifically, precipitation was shown to become progressively more complex from the mountainous area in the northwest to the plain area in the southeast; whereas, the complexity of air temperature exhibited an opposite trend with less complexity in the plain area. Overall, the spatial patterns of the complexity of precipitation and air temperature reflected the influence of the dominant climate system in the region.