Algorithm complexity identification

摘要

An illustrative embodiment provides a computer-implemented process for algorithm complexity identification through inter-procedural data flow analysis receives a call graph to form a set of received nodes in a static analysis framework, identifies a parent node in the set of received nodes to form an identified parent, traverses the call graph from the identified parent node to a node to identify a function within the node to form an identified function. Each identified function is analyzed to form a complexity value in a set of complexity values. Responsive to a determination that node analysis is complete, and responsive to a determination that path analysis is complete, determines whether path analysis for the identified parent is complete. Responsive to a determination that path analysis for the identified parent is complete, sum the complexity values in the set of complexity values for the identified parent and return the complexity value for the identified parent to a requester.

主权项

1. A method, comprising:
receiving, in a static analysis framework, a call graph; identifying a parent node of the call graph; traversing the call graph from the parent node to a first child node along a first path of the call graph; identifying a first function within the first child node; analyzing the first function to form a first complexity value; responsive to a determination that analysis of the first child node is complete, determining whether analysis of the first path is complete; responsive to a determination that analysis of the first path is complete, calculating a parent complexity value; responsive to a determination that analysis of the first path is not complete, traversing the call graph to a second child node of the first path; identifying a second function within the second child node; analyzing the second function to form a second complexity value; and calculating the parent complexity value as the sum of the first complexity value and the second complexity value.