Какова сложность во время выполнения этого кода, который содержит четыре рекурсивных вызова?

Question

какова его сложность во время выполнения, которая имеет 4 рекурсивных функции.

def func(arr,i,j,N):

  if i==N or j==N or i<0 or j<0: 
     return
  if arr[i][j]==1 or arr[i][j]=='X': 
     return

  arr[i][j]='X' 

  func(arr,i,j+1,N) 
  func(arr,i,j-1,N) 
  func(arr,i+1,j,N) 
  func(arr,i-1,j,N) 

  return(arr)

Answer 1

Давайте сначала рассмотрим аналитический подход. Мы можем попробовать запустить функцию с меньшим Ns и найти шаблон.

import numpy as np


global call_cnt

def cc(arr,i,j,N):

  global call_cnt

  call_cnt += 1
  #print(call_cnt)

  if i==N or j==N or i<0 or j<0:
     return
  if arr[i][j]==1 or arr[i][j]=='X':
     return

  arr[i][j]='X'

  cc(arr,i,j+1,N)
  cc(arr,i,j-1,N)
  cc(arr,i+1,j,N)
  cc(arr,i-1,j,N)

  return(arr)


n_On = []

for i in range(1,30):
  global call_cnt

  call_cnt = 0

  cc(np.zeros((i,i)).tolist(), 0, 0, i)

  print(call_cnt)
  n_On.append(call_cnt)

import matplotlib.pyplot as plt

plt.plot(n_On)
plt.show()

1. Мы инициализировали массивы с ненулевыми значениями, чтобы мы не соответствовали базовому случаю arr [i] [j] == 1, поэтому программа будет работать в худшем случае.

2. После 29 мы получаем максимальную глубину рекурсии, поэтому мы просто выбрали 1-29 для нашего N.

3. После построения графика числа общее количество вызовов для каждого N, мы получаем этот график.

5
17
37
65
101
145
197
257
325
401
485
577
677
785
901
1025
1157
1297
1445
1601
1765
1937
2117
2305
2501
2705
2917
3137
3365

Теперь мы можем подобрать эти точки, используя множество Линии регрессии, одна вещь наверняка не экспоненциальная.

После небольшой настройки с числами, вы можете увидеть, что функция 4xN^2 очень близка к ней, на самом деле, значения идеально подходят 4xN^2 + 1 функция.

Давайте попробуем представить эту функцию поверх числа вызовов.

import matplotlib.pyplot as plt

plt.plot(n_On)
plt.plot([4*(i**2) + 1 for i in range(1,30)], 'k+')
plt.xlabel('N')
plt.ylabel('number of calls')
plt.show()

Это идеально подходит!

Теперь, почему? В вашей рекурсивной функции у вас есть в основном 2 переменные, которые меняют i и j. Поскольку i и j меняются только в диапазоне N (из-за вашей проверки i, j> 0 и i, j NxN -> N ^ 2), и вы также использовали мемоизацию (не посещая уже посещенные ячейки ), так что в общем N ^ 2.

Наконец, для каждого случая есть 4 вызова. Отсюда и эта сложность.

Итак, это O(N^2).

Answer 2

Думайте о сетке как о графике с точками сетки как вершинами, а ребрами являются отрезки между соседними точками сетки.

количество узлов равно N^2, и вы посещаете каждый из их, поэтому алгоритм обязательно \Theta(N^2). При этом вы следуете за каждым ребром ровно один раз (после первого посещения ребра обе конечные точки помечаются 1 или X, поэтому ни для одной из конечных точек поток программы никогда не достигнет рекурсивных вызовов).

Количество ребер 2N(N-1). Таким образом, al go работает в O(N^2).

Answer 3

Это O (N ^ 2). Каждую ячейку посещают не более одного раза от каждого из ее соседей, поэтому существует не более 4N (N-1) вызовов функций (исключая те, которые go выходят за пределы, из которых максимум 4N). Вы можете добавить счетчик, который увеличивается каждый раз, когда func вызывается для проверки.