## 4 Optimization of Balanced Partition Routing Algorithm
### Computational Complexity Analysis under Two Partitioning Methods
Minimum computing force requirements for a single node:  
\[\text{C}_{\text{method 2 node}}(\text{N})=\left(\sum\limits_{\text{m}=0}^{ \frac{N}{2}-1}\frac{\left(\frac{N}{6}-2\right)!}{\left(\frac{N}{6}-2-\text{m} \right)!}+\delta_{2}+\left(\frac{N}{6}\right)^{2}+\left(\frac{N}{3}\right)^{2}\right) \tag{17}\]  
Total algorithm complexity:  
\[\text{C}_{\text{method 2(N)}}=\text{U}_{1}+\text{U}_{2}\] \[\text{U}_{1}=\frac{\frac{N}{2}-1}{N-1}\left(\sum\limits_{\text{ m}=0}^{\frac{N}{2}-2}\frac{\left(\frac{N}{6}-2\right)!}{\left(\frac{N}{6}-2- \text{m}\right)!}+\delta_{2}\right)+\frac{\frac{N}{6}}{N-1}\left(2\sum\limits_ {\text{m}=0}^{\frac{N}{2}-2}\frac{\left(\frac{N}{6}-2\right)!}{\left(\frac{N} {6}-2-\text{m}\right)!}+\delta_{2}\right)+\left(\frac{N}{6}\right)^{2}\right)\] \[\text{U}_{2}=\frac{\frac{N}{2}}{N^{2}-1}\left[\left(2\cdot\left( \sum\limits_{\text{m}=0}^{\frac{N}{2}-2}\frac{\left(\frac{N}{6}-2\right)!}{ \left(\frac{N}{6}-2-\text{m}\right)!}+\delta_{2}\right)+\left(\frac{N}{3} \right)^{2}\right)+2\cdot\left(3\cdot\left(\sum\limits_{\text{m}=0}^{\frac{N} {2}-2}\frac{\left(\frac{N}{6}-2\right)!}{\left(\frac{N}{6}-2-\text{m}\right)!} +\delta_{2}\right)+\left(4\cdot\left(\sum\limits_{\text{m}=0}^{\frac{N}{2}-2} \frac{\left(\frac{N}{6}-2\right)!}{\left(\frac{N}{6}-2-\text{m}\right)!}+ \delta_{2}\right)+\left(\frac{N}{3}\right)^{2}+2\cdot\left(\frac{N}{6}\right)^{2 }\right)\right]\]  
Simplified to obtain:  
\[\text{C}_{\text{method 2(N)}}=\frac{\frac{N}{6}-1}{N-1}\cdot\left(\sum\limits_{ \text{m}=0}^{\frac{N}{6}-2}\frac{\left(\frac{N}{6}-2\right)!}{\left(\frac{N}{6 }-2-\text{m}\right)!}+\delta_{2}\right)+\frac{\frac{N}{6}}{N-1}\cdot\left(14 \cdot\left(\sum\limits_{\text{m}=0}^{\frac{N}{6}-2}\frac{\left(\frac{N}{6}-2 \right)!}{\left(\frac{N}{6}-2-\text{m}\right)!}+\delta_{2}\right)+3\cdot\left( \frac{N}{3}\right)^{2}+4\cdot\left(\frac{N}{6}\right)^{2}\right)\]  
\[\delta_{2}=\frac{\left(\frac{N}{6}-2\right)\cdot\frac{N}{6}}{2}+\delta_{\text{ recall}} \tag{18}\]  
**Method 3:** As shown in Figure 5, method 3 is similar to method 1. Nodes in the system are evenly divided into more small groups. All nodes are divided into six groups. To calculate the routing path from star node numbered i to star node numbered j, there may be two cases to consider. 1. In the first case, the two star nodes are in the same small group and the routing path is calculated directly in the group. In the second case, the two nodes are not in the same group. Assuming that the two communication nodes of the groups these two nodes belong to are numbered i + x and j + y, respectively. Therefore, the total routing path is going to be: i-y+i+x-j+y-j. Minimum computing force requirements for a single node: \[\text{C}_{\text{method 3 node}}(\text{N})=\sum_{\text{m}=0}^{\frac{N}{2}-1} \frac{\left(\frac{N}{6}-2\right)!}{\left(\frac{N}{6}-2-\text{m}\right)!}+ \left(\frac{N}{6}\right)^{2}+\delta_{2}\] (19) Total algorithm complexity: \[\text{C}_{\text{method 3}}(\text{N})=\left(\frac{\frac{N}{6}-1}{N-1} \cdot\sum_{\text{m}=0}^{\frac{N}{2}-1}\frac{\left(\frac{N}{6}-2\right)!}{ \left(\frac{N}{6}-2-\text{m}\right)!}+\delta_{2}+\frac{\frac{5N}{6}}{N-1}\cdot \left(\left(\frac{N}{6}\right)^{2}+\left(\sum_{\text{m}=0}^{\frac{N}{2}-1} \frac{\left(\frac{N}{6}-2\right)!}{\left(\frac{N}{6}-2-\text{m}\right)!}+ \delta_{2}\right)\cdot 5\right)\right)\cdot\text{N}^{2}\] (20) Then: \[\text{C}_{\text{method 2}}(\text{N})-\text{C}_{\text{method 3 node}}(\text{N})= \left(\frac{N}{3}\right)^{2}>0\] (21) \[\text{C}_{\text{method 2 node}}(\text{N})=\left(\sum\limits_{\text{m}=0}^{ \frac{N}{2}-1}\frac{\left(\frac{N}{6}-2\right)!}{\left(\frac{N}{6}-2-\text{m} \right)!}+\delta_{2}+\left(\frac{N}{6}\right)^{2}+\left(\frac{N}{3}\right)^{2}\right) \tag{17}\]0 (22) Therefore, both the computational complexity of a single node and the total computational complexity of method 2 is greater than that of method 3.