python - 计算python中递归算法中的操作数

Question

我在 python 中实现了 dichotomic search 算法，在函数的第二个版本中我必须(除了根据元素的存在与否返回 true 或 false 之外)计数算法完成的操作(比较)的数量取决于我正在处理的列表的长度并返回它。

但是，我的函数是递归的，自然我必须将计数器变量(每次操作都会递增)初始化为零。问题是这个变量在每次递归调用时都会取零值，因此它不会给我正确的值。想到了全局变量，但是不知道怎么用。

这是我的函数代码:

def trouve(T, x) :      
  if len(T) == 0 :
    return False 
  mid = len(T) // 2
  if T[mid] == x :
    return True
  if len(T) == 1 and T[0] != x  : 
    return False
  else :
    if x > T[mid] :
      return trouve(T[mid:], x)
    else :
      return trouve(T[:mid], x)

Answer 1

通常，您只会计算数据的比较，而不是比较输入列表长度的条件。

您可以使用第三个参数来累积计数，然后让函数返回成功和计数的元组:

def trouve(T, x, c = 0):
  if len(T) == 0:
    return (False, c) # len() comparisons do not count 
  mid = len(T) // 2
  if T[mid] == x:
    return (True, c+1)
  if len(T) == 1: # you don't need to compare x again here! 
    return (False, c+1)
  # you don't need `else` here
  if x > T[mid]:
    return trouve(T[mid:], x, c+2)
  # you don't need `else` here
  return trouve(T[:mid], x, c+2)

print (trouve([1,3,8,13,14,15,20], 14))

请注意，您可以稍微优化一下:

def trouve(T, x, c = 0):
  if len(T) == 0:
    return (False, c) 
  mid = len(T) // 2
  # you don't need the `len(T) == 1` case, as it can be 
  # treated in the recursive call. See change below:
  if x > T[mid]:
    return trouve(T[mid+1:], x, c+1) # exclude mid itself
  # Move equality test below greater-then test, since the 
  # equality has little chance of being true:
  if T[mid] == x:
    return (True, c+2)
  return trouve(T[:mid], x, c+2)

print (trouve([1,3,8,13,14,15,20], 14))

...虽然对于我给出的示例，此版本中的计数仍然相同。