Estimating Minimum Operation Steps via Memory-based Recurrent Calculation Network

To estimate time complexity for a given algorithm is important for algorithm designers. Usually, time complexity means the "analytical" time complexity which needs to be proved by strict math derivation. We propose to estimate the "numerical" time complexity (NTC), which measures the minimum number of operations an algorithm has to spend, as well as capture the intrinsic laws of time complexity. The unique challenges include: (1) How to make a machine learning model has the same ability as a real-world CPU (2) How to measure the minimum number of required arithmetic operations for a given problem. To tackle these challenges, we first propose a memory-based recurrent calculation network to mimic the functions of CPU and then we propose a self-adaptive selection gate for deciding when the mimic calculation process should stop. In addition, we use a symbolic learning method to find the time complexity formula. We train and test our model on four basic algorithms: long integer addition, 1-dim max-pooling, outer product, and sorting. Experiment results demonstrate that our model can precisely predict the numerical time complexity as well as the time complexity formula for each algorithm. We also conduct many visualizations to prove the effectiveness and correctness of our model.