当我们谈论算法我们在谈论什么:由疫情核酸检测想到的分治算法(Divide-and-Conquer)

    北京的疫情一波未平一波又起,由此看来,战“疫”将是一场旷日持久的战争,绝不能掉以轻心、轻易言胜。病毒随时都会死灰复燃,以生命为代价换来的经验教训值得我们每一个人久久深思。笔者所在的小区也开始组织居民批量进行核酸检测,本以为会是一幅摩肩接踵,水泄不通的场景,却出人意料的井然有序、有层有次,效率非常高。原来检疫部门采取了一种特别的策略:每五个人用一组试剂盒,进行快筛,分分钟搞定了几百人的社区检测。

    这里解释一下病毒核酸检测的原理,检测人员提取小区居民的鼻腔拭子或者咽拭子(就是用一根棉签在咽喉处或者鼻腔深处刮取一些分泌物),然后将该棉签放入试剂盒,以病毒独特的基因序列检测靶标,通过PCR扩增,使我们选择的这段靶标DNA序列指数级增加,每一个扩增出来的DNA序列,都可与我们预先加入的一段荧光标记探针结合,产生荧光信号,扩增出来的靶基因越多,累计的荧光信号就越强。说白了就是试剂盒荧光反映变色越强烈,说明病毒体量和活性越强。

    而五人一组共用一个试剂盒测试,如果结果呈阳性,再对其中四个人分别测试即可。 由于绝大部分人都是健康的,所以这样可以提高五倍的检测量,从而检测更多的人,很明显这次检疫使用到了类似归并的“分治法”来解决问题,提高效率。

    分治法,即“分而治之”,出自清·俞樾《群经平议·周官二》“巫马下士二人医四人”:“凡邦之有疾病者,疕疡者造焉,则使医分而治之,是亦不自医也。” 其核心思想是:将一个难以直接解决的大问题,分拆成一些规模较小的相同问题,随后各个击破,分而治之。可以理解为:如果原问题可以分割成n个子问题,1<n<=原问题,且这些子问题均可解并且利用这些子问题的解求出原问题的解,那么分治方法就是可行的。由分治法产生的子问题往往是原问题的较小模式,这就为使用递归算法提供了遍历。反复应用分治手段,可以使子问题与原问题类型一致而其规模却不断缩小,最终使子问题缩小到很容易直接求出其解。这自然导致递归的使用。所以分治与递归经常同时应用在算法解决方案中。

    核酸检测正好契合分治算法的使用场景:该问题的规模只要缩小到一定的规模就可以容易的解决。该问题可以分解为若干个规模较小的相同问题(检测是否阳性)。

    而我们在技术面试中,可以利用分治算法解决的经典问题如下:

    归并排序

def merge_sort(lst):
# 从递归中返回长度为1的序列
if len(lst) <= 1:
return lst

middle = len(lst) / 2
# 1.分解:通过不断递归,将原始序列拆分成 n 个小序列
left = merge_sort(lst[:middle])
right = merge_sort(lst[middle:])
# 进行排序与合并
return merge(left, right)

def merge(left, right):
i, j = 0, 0
result = []
# 2.解决:比较传入的两个子序列,对两个子序列进行排序
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
# 3.合并:将排好序的子序列合并
result.extend(left[i:])
result.extend(right[j:])
return result

    快速排序

def quickSort(listx):
if len(listx)<=1:
return listx
pivot = listx[len(listx)//2] #取列表中中间的元素为被比较数pivot
listl = [x for x in listx if x < pivot] #<pivot的放在一个列表
listm = [x for x in listx if x ==pivot] #=pivot的放在一个列表
listr = [x for x in listx if x > pivot] #>pivot的放在一个列表
left = quickSort(listl) #递归进行该函数
right = quickSort(listr) #递归进行该函数
return left + listm + right #整合
print(quickSort([9,3, 6, 8, 9, 19, 1, 5])) #[1, 3, 5, 6, 8, 9, 9, 19]

    折半查找

def binary_search(lis, key):
low = 0
high = len(lis) - 1
time = 0
while low < high:
time += 1
mid = int((low + high) / 2)
if key < lis[mid]:
high = mid - 1
elif key > lis[mid]:
low = mid + 1
else:
# 打印折半的次数
print("times: %s" % time)
return mid
print("times: %s" % time)
return False

    二叉树的最大深度问题

class Solution(object):
def maxDepth(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if not root:
return 0
left = self.maxDepth(root.left) + 1
right = self.maxDepth(root.right) + 1
return left if left > right else right

    计算x 的 n 次幂问题

class Solution(object):
def myPow(self, x, n):
"""
:type x: float
:type n: int
:rtype: float
"""
if not n:
return 1
if n < 0:
return 1 / self.myPow(x, -n)
if n % 2:
return (x * self.myPow(x, n - 1))
return self.myPow(x * x, int(n / 2))

    当然了,分治算法也并非无懈可击,回到核酸检测的场景,这种做法在最乐观情况下,的的确确是提升了五倍的效率,但是在最不乐观情况下,反而会增大工作量。如果在检测这些人中一个感染的患者都没有,那就是最乐观情况,5人一组检查一遍就OK了;如果这群人全部(正确来讲是在分组后的每一组中都有至少一个)感染人员,这种极端恶劣的情况下会导致至少增加分组数量的工作量,所以根本问题又变成了在假设一定感染率的情况下,如何确定多少个样本一组检测比较好。考虑的因素可能包括,检测效率,费用,有阳性的时候快速定位等。实际监测的时候,还可以不同地区不同的检测策略,监测策略也可以根据检测结果调整。

    结语:算法其实在生活中无处不在,很多同学出去面试时往往惧怕做算法题,其实算法也不过就是一种解决问题的方法,目的也仅仅是为了提高效率,如果在生活中多观察、多思考,也许会对算法能力的提升有一定的帮助。