# A Knowledge and Semantic Fusion Method for Automatic Geometry Problem Understanding
## 5 Information Detect and Interpret Model
### Method Complexity Analysis  
Template Matching Complexity. Traditional template-based methods require designing separate templates for each linguistic variant of a relationship, leading to exponential growth in template quantity as relational complexity increases. If a relationship has \(V\) linguistic variants and involves \(k\) concurrent relationships, the total number of templates \(T\) becomes \(O(R\cdot V^{k})\) (\(R\): relationship types). This exponential scaling makes template matching prohibitively expensive, as it requires traversing all templates, resulting in exponential time complexity \(O(R\cdot V^{k})\).  
In contrast, the proposed dynamic template approach addresses this issue through two key improvements: tree-structure knowledge management, allowing that during matching, only the subtree of the current relational branch is traversed, avoiding full-template searches, and the reusable component-based template framework RSF, where only a total of eight RSFs need to be predefined and templates are dynamically generated instead of being independently designed. With dynamic pruning (skipping failed templates) and priority sorting (high-frequency templates prioritized), template matching complexity is reduced from the traditional exponential to a linear \(O(R)\).  
Text-level ERE Complexity. The text-level ERE process (IDIM-T) involves sentence splitting, keyword detection, template matching, and structured generation. The input problem text is split into clauses, with linear complexity \(O(N)\) (\(N\): number of clauses). For each clause, scan keywords using a hash-indexed dictionary (key: keyword, value: relationship type), reducing complexity from \(O(N\cdot K\cdot R)\) (\(K\): the average number of keywords per clause) to \(O(N\cdot K)\). For each detected keyword, load its corresponding RSF from SGKO, which incurs a complexity of \(O(N\cdot K\cdot C)\) (\(C\): the fixed number of RSFs, \(C\leq 8\)), ultimately remaining at \(O(N\cdot K)\). Finally, generating relationship triples incurs a complexity of \(O(E)\) (\(E\): total entities). Thus, the total time complexity for this stage reaches linear \(O(N\cdot K)\).  
Knowledge-level ERE Complexity. The text-level ERE process (IDIM-K) includes entity decomposition, relationship construction and entity deduplication. Breaking down non-atomic entities into lower dimensions has a complexity of \(O(M)\) (\(M\): total entities, including both original and dimension-decomposed entities), and the same applies to relationship construction. Then, hash-based deduplication introduces a complexity of \(O(M\cdot logM)\). Consequently, the total time complexity for this stage reaches a linearithmic level of \(O(M\cdot logM)\).  
Overall Pipeline Complexity. Combining the text-level and knowledge-level processes, the total end-to-end pipeline complexity is \(O(N\cdot K+M\cdot\log M)\). This represents a significant improvement from the original exponential or polynomial complexities to a linearithmic level (even the worst-case complexity).  
The proposed method achieves a breakthrough in complexity by reducing the exponential complexity of traditional template matching to linear complexity through tree-structured knowledge management and dynamic, component-based template generation. This optimization not only improves the efficiency of the text-level ERE process but also ensures that the overall pipeline remains scalable and practical, even for complex geometry problem understanding tasks. More detailed comparisons are summarized in Table 7.