Time Complexity of Recursive Algorithm

  Algorithm complexity

Recursive algorithm should be familiar to everyone, in fact, recursion should be met at the beginning in math class, similar to f(x)=f(x-1)+f(x+1), f(1)=1, f(2)=4, f(3)=3, this kind of math problem we should have seen many, in fact, the idea is recursion layer by layer, and finally the target value is expressed by f(1), f(2), f(3).

Before doing a requirement, we need to realize the function similar to operating system folder. We use MySQL database to record data. The table field has 4 columns, which are id, index_name, pid, is_directory, index_name to record the file or file name, pid to record its parent id, is_directory to mark whether it is a file or a folder. After the records are saved, the problem of data retrieval is involved. The target data structure required by our front end is as follows

[{"id":1,"name":"./"},{"id":2,"name":"./1.txt"},
{"id":3,"name":"./dir1/"},
{"id":4,"name":"./dir1/2.txt"},...]

It is somewhat similar to the tree command of linux system.

The first version of the code looks like this:

tree = []
def getTree(pid):
              return
for index in childIndexes:
 if len(tree) == 0:
   if index.is_directory==1                            tree.append(
{'id':index.id,'name':'./'+index.index_name+'/'})                     
getTree(index.id)
                     else:                            
tree.append(
{'id':index.id,'name':'/'+index.index_name})
              else: 
                    for item in tree:  
if item['id'] == index.id
                                   if item.is_directory==1:                                          tree.append({'id':index.id,'name': 
item['name']+index.index_name+'/'})    
                               else:  
                                        tree.append
(
{'id':index.id,'name':item['name']+index.index_name
}
)

Let’s take a look at the time complexity of this algorithm. The time complexity of the first layer is n, the time complexity of the second layer is n, the time complexity of the inner layer is o (n 2), plus recursion, the final time complexity is o (2 n * n 2). This algorithm is very rough. If the recursion depth is 100, the final execution efficiency will make people feel numb. Next, let’s consider how to optimize.

Second Edition Code:

tree = []
def getTree(pid,path='./'):
              return
       for index in childIndexes:
             if len(tree) == 0: 
                    if index.is_directory==1                            tree.append({'id':index.id,
'name':path+index.index_name+'/'}) 
                           getTree(index.id, 
path+index.index_name+'/')
                    else:
                           tree.append({'id':index.id,
'name':path+index.index_name}) 
             else: 
                    if item.is_directory==1:                            tree.append({'id':index.id,
'name':path+index.index_name+'/'})
                     else: 
                           tree.append({'id':index.id,
'name':path+index.index_name})

We use variables to save each path. This time we will look at the time complexity. The first layer traversal time complexity is O(n), plus recursion, the final time complexity is o (2 n * n), which is not ideal, at least better than the first time.

Let’s take a look at a common interview topic, Fibonacci sequence, n=1,1,3,5,8,13 …, what is the number n?

A look at the first thought of recursive way:

def fibSquence(n):     
  if n in (1,2):       
   return 
   fibSquence(n-1)+ fibSquence(n-2)

The time complexity of this algorithm is O (2 n), which can be understood from the number of calls. Let’s consider how to optimize, for example, to find n=3 is, we need to find n = 2 and n = 1 first, but we have already found n = 1 and n = 2 at the beginning, which is two more steps of repeated calculation.

The following is the optimized code:

fibMap = {1:1,2:2}
def fibSquence(n):
       else:
        result = fibSquence(n-1)+ fibSquence(n-2)              fibMap.update({n:result})
              return result

We use map to register the intermediate value, map is implemented based on hash, and the time complexity is O(1), so the time complexity of this algorithm is O(n).

But in fact this problem need not be solved recursively.

fibMap = {1:1,2:2}
def fibSquence(n):
       else:
              for i in range(3,n+1): 
                    fibMap.update({i:fibMap[i-1]+fibMap[i-2]})
              return fibMap[n]

In this way, we can find the target value with only one traversal.

The optimization of recursive algorithm is probably to avoid repeated operations and save the gold state for the next use. structurally, it is to convert the time complexity into the space complexity to solve the problem. The efficiency of recursion algorithm is actually very low. You can try not to use recursion without recursion. Of course, we should also deal with specific problems. For example, I started to mention the problems encountered in my project. I really can’t think of any better way to solve them without recursion.

Author: Yang YiYixin Institute of Technology