时间戳

首页 > 解决方案 > 有和没有记忆的回溯算法的复杂性

python - 有和没有记忆的回溯算法的复杂性

问题描述

问题如下：

我们的输入是一个由 14 个数字组成的数组，我们的输出是这是否是一手获胜的手牌。为了使一手牌成为赢手，必须可以按照以下规则将其号码分成几组：

  1. 每组 3 必须是相同的数字或顺子（111 或 123）
  2. 我们只允许拥有一对相同的数字（22 可以，但 45 不行）

例如：

[1,1,1,2,2,2,3,3,3,4,4,4,5,5]: True
[1,1,1,2,2,2,3,3,3,4,4,4,5,6]: False
[1,1,2,2,3,3,4,4,4,6,6,6,8,8]: True

我使用回溯技术为问题编写了以下解决方案：

注意：忽略它的所有出现seen是我下面问题第二部分的记忆的一部分。

def is_winning_hand(hand):
  hand.sort()
  seen = set()
  return is_winning_hand_step(hand, True, seen)
  
def is_winning_hand_step(hand, can_take_two, seen):
  if len(hand) == 0:
    return True
    
  if len(hand) == 1:
    return False
    
  if str(hand)+str(can_take_two) in seen:
    return False
    
  if can_take_two:
    valid, new_hand = take_two(hand)
    if valid:
      if is_winning_hand_step(new_hand, False, seen):
        return True
    
  if len(hand) >= 3:
    valid, new_hand = take_three(hand)
    if valid:
      if is_winning_hand_step(new_hand, can_take_two, seen):
        return True
          
    valid, new_hand = take_straight(hand)
    if valid:
      if is_winning_hand_step(new_hand, can_take_two, seen):
        return True
        
  seen.add(str(new_hand)+str(can_take_two))
  return False

def take_two(hand):
  if hand[0] == hand[1]:
    return True, hand[2:]
  else:
    return False, None
    
def take_three(hand):
  if hand[0] == hand[1] and hand[1] == hand[2]:
    return True, hand[3:]
  else:
    return False, None

def take_straight(hand):
  cnt = 1
  last_val = hand[0]
  indices = set([0])
  
  for i in xrange(1, len(hand)):
    if hand[i] == last_val:
      continue
    elif hand[i] == last_val + 1:
      cnt += 1
      indices.add(i)
      last_val = hand[i]
      if cnt == 3:
        return True, [x for j, x in enumerate(hand) if j not in indices]
    else:
      return False, None
      
  return False, None

现在我试图找出这个问题的时间复杂度。让我们假设输入已经为我们排序，所以把它放在一边O(N log N)。

我的猜测是，因为在每一步中我都有可能拆分为 3 个分支，所以复杂性是O(3^N)其中 N 应该是输入数组的长度。在我们的例子中，它总是 14 长度的数组，但我说的是一般情况。我对么？

在下一步中，我在我的解决方案中添加了一个记忆。我们现在可以说一下时间复杂度吗？多亏了记忆，我一次又一次地避免解决相同的子问题，所以这是一个O(N)解决方案吗？

标签： pythontime-complexitybacktrackingrecursive-backtracking

解决方案

推荐阅读