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

Question

我在python中实现了二分法搜索算法，在函数的第二个版本中，我必须（除了根据元素的存在与否返回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

通常，只计算数据的比较，因此不计算比较输入列表长度的条件。你知道吗

可以使用第三个参数累积计数，然后让函数返回success和count的元组：

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
  # ...

在较大的程序中使用这些名称时要小心，因为可能会意外地使用同一全局名称两次，从而导致问题。你知道吗