您的位置: 首页  >  文章  >  《算法图解》（四）

《算法图解》（四）

分类: 文章 • 2023-10-16 22:51:33

欧几里得算法–求最大公约数

内容：gcd(x,y) = gcd(y,x mod y)
证明：假设求 x , y 最大公约数 m，且 x > y，令 a = x / y , b = x % y
   则有： x = y*a + b
   因为 x 和 y 均能被m整除，易得 b 也能被 m 整除，求x与y的最大公约数就是求y 和 b 的最大公约数，即 gcd(x,y) = gcd(y,x mod y)

分治算法

通过介绍三个实例来理解

  • 假设你是农场主，有一小块土地。 你要将这块地均匀地分成方块，且分出的方块要尽可能大。《算法图解》（四）
    首先直观的想法就是求边长的最大公约数，那怎么求解呢？如何采用分治法？
    将这个大的田地以宽为边划分出正方形，如图：
    《算法图解》（四）
    再将余下的土地按照刚才的方式继续划分，《算法图解》（四）
    那么基线条件是直到边的长度恰好是宽的长度的整数倍，此时的正方形是
    “适用于这小块地的最大方块，也是适用于整块地的最大方块”
  • 利用递归求解求和问题
    第一步：找出基线条件。最简单的数组什么样呢？请想想这个问题，再接着往下读。如果数 组不包含任何元素或只包含一个元素，计算总和将非常容易。 《算法图解》（四）
    第二步：每次递归调用都必须离空数组更近一步。如何缩小问题的规模呢？下面是一种办法。
    《算法图解》（四） 
def sun(alist):
    if len(alist)==0:
        return 0
    else:
        return alist[0]+sum(alist[1:])
print(sun([1,3,6]))

快排

思路：选定基准值，确定分区
《算法图解》（四）
代码：

def quicksort(alist):
    if len(alist) <= 1:
        return alist
    else:
        povit = alist[0]
        small = [i for i in alist[1:] if i<povit]
        large = [j for j in alist[1:] if j>povit]
        return quicksort(small)+[povit]+quicksort(large)
print(quicksort([1,4,2,5,3,7]))

时间复杂度：平均情况和最好的情况都是O(nlgn)，最坏的情况下是O(n2)。
快速排序的性能高度依赖于你选择的基准值。假设你总是将第一个元素用作基准值，且要处理的数组是有序的。由于快速排序算法不检查输入数组是否有序，因此它依然尝试对其进行排序。
所用的调用栈的高度为如下，由于数组是有序的，每次分区都会有一个数组为空，导致调用栈非常长。
《算法图解》（四）
现在假设你总是将中间的元素用作基准值，在这种情况下，调用栈如下。
《算法图解》（四）
无论基准值选择哪个位置，再每一层的调用栈里，算法执行所用时间都是O(n)，。因此整个算法需要的时间为O(n) * O(log n) = O(n log n)。这就是最佳情况。 在最糟情况下，有O(n)层，因此该算法的运行时间为O(n) * O(n) = O(n2)。

小结

 D&C将问题逐步分解。使用D&C处理列表时，基线条件很可能是空数组或只包含一个元 素的数组。
 实现快速排序时，请随机地选择用作基准值的元素。快速排序的平均运行时间为O(n log n)。
 大O表示法中的常量有时候事关重大，这就是快速排序比合并排序快的原因所在。
 比较简单查找和二分查找时，常量几乎无关紧要，因为列表很长时，O(log n)的速度比O(n) 快得多。

相关推荐