计算Python中递归算法中的作用数量

Question

我正在在python中实现二分法搜索是否存在该元素的存在）计算该算法完成的操作数（比较），具体取决于我正在使用的列表的长度并返回。

但是，我的功能是递归的，自然而然，我必须初始化一个计数器变量（每次操作都会增加）至零。问题在于，该变量将在每个递归调用中取零值，因此，它不会给我正确的值。我想到了一个全球变量，但我不知道如何使用它。

这是我功能的代码：

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))

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

Answer 2

如果您想进入全局变量路由（既然您提到了），这就是您的方式。

trouve_count = 0
def trouve(T, x) :
  global trouve_count
  # Increment trouve_count like this when necessary:
  trouve_count += 1
  # ...

在较大的程序中要小心使用它们，因为您可能会意外使用相同的全局名称，从而引起问题。