# An Enhanced Multi-Constraint Optimization Algorithm for Efficient Network Topology Generation
## 4 Algorithm Design
### Time Complexity Analysis of the Algorithm  
Proof: We first analyze the time complexity for the initial link creation algorithm, which creates inter-satellite links. The outer loop runs \(n\) iterations, where \(n\) denotes the number of nodes. The inner loop iterates through all neighbors of each node, which can be as many as \(n\) in the worst case. Operations within the inner loop, such as checking visibility, communication constraints, and potentially adding a link, have a constant time complexity \(O(1)\). Thus, this part of the algorithm exhibits a time complexity of \(O(n^{2})\).  
Next, we consider the link pruning process. Like before, the outer loop runs \(n\) iterations. The inner while loop continues as long as a node's degree remains greater than \(d\). In the worst case, this could be \(n\). The operations within the while loop, finding and removing the link with the smallest weight, may have a time complexity of \(O(n)\) if implemented inefficiently. However, it could be solved in \(O(\log n)\) time. Therefore, in the worst case, this part of the algorithm has a time complexity of \(O(n^{2}\log n)\).  
Regarding the multi-attribute decision-making weight algorithm, the following steps are performed: initializing the constellation network topology, calculating the average link length, and computing the average link duration. These operations generally have time complexities of \(O(n)\) or \(O(m)\), where \(n\) represents the number of nodes, and \(m\) denotes the number of links. Combining the complexities, the total time complexity of the link creation algorithm amounts to \(O(n^{2})+O(n^{2}\log n)=O(n^{2}\log n)\) in the worst case.  
When iterating through each node in the constellation network, the outer loop runs \(n\) times, where \(n\) is the number of nodes in the network. Inside this loop, we perform the following tasks: (a) building a multi-attribute decision matrix \(D\) with complexity \(O(n*a)\), where \(a\) is the attribute count; (b) normalizing \(D\) to obtain \(R\), which also has a complexity of \(O(n*a)\), assuming that all matrix entries are visited; (c) computing \(p_{ij}\), \(S_{j}\), \(h_{j}\), and \(q_{j}\), each with a complexity of \(O(n)\), as they involve sums over \(n\); (d) obtaining the attribute  
Figure 3: The flowchart of MCOTG algorithm.  
weight vector \(Q\), an \(O(1)\) operation; (e) calculating \(W=D*Q\), with complexity \(O(n^{2})\), since \(D\) is an \(n\times n\) matrix.  
For the link deletion algorithm, the outer loop runs \(n\) times, where \(n\) is the number of nodes in the graph. Inside this loop, we: (a) initialize the node in constant time, \(O(1)\); (b) perform an \"if condition\" check; (c) sort the links of a node according to their weights, an operation with time complexity \(O(m\log m)\), where \(m\) is the number of links associated with a node. In the worst case, \(m\) could be as large as \(n\), resulting in a complexity of \(O(n\log n)\).  
When analyzing the three algorithms' time complexities separately, we obtain the following results: Initial Link Creation Algorithm: \(O(n^{2}\log n)\); Multi-Attribute Decision-making Weight Algorithm: \(O(n^{2}*a)\), where \(a\) is the number of attributes; Link Deletion Algorithm: \(O(n^{2}\log n)\) or potentially \(O(n^{3})\) if edge deletion is an \(O(n)\) operation. Since the algorithms form parts of a larger algorithm sequentially, the total time complexity is the maximum of these three, as they do not depend on each other and do not form nested loops. If edge deletion can be performed in constant time, the total time complexity is \(O(n^{2}\log n)\).