欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Summary--算法图解

程序员文章站 2022-06-07 14:38:35
...

本文主要补充《我的第一本算法书》总结缺失的,以python为主要实现方式

一. 关于O:

  1. 一些常见的大O运行时间:将大O转换为操作数进行化简
    Summary--算法图解

二. 选择排序:

  1. 数组读取是O(1)插入是O(n),相反链表读取是O(n) 插入是O(1)
  2. 所有函数调用都进入调用栈
  3. 快速排序使用分而治之的策略(D&C)。思想是:找到基线条件不断将问题分解。
    Summary--算法图解
    Summary--算法图解
    Summary--算法图解
    Tip:编写涉及数组的递归函数时,基线条件通常是数组为空或者只包含一个元素。陷入困境时,请检查基线条件是不是这样的!
    补充:
    Summary--算法图解
  4. 思想明白了之后,就讲一讲c语言标准库的
    qsort,即快排。。对排序算法来说,最简单的数 组什么样呢?还记得前一节的“提示”吗?就是根本不需要排序的数组。因此,基线条件为数组为空或只包含一个元素。在这种情况下,只需 原样返回数组——根本就不用排序
    归纳证明:归纳证明是一种证明算法行之有效的方式。它分两步:基线条件和归纳条件。对于快速排序,可使用类似的推理。在基线条件中,我证明这种算法对空数组或包含一个 元素的数组管用。在归纳条件中,我证明如果快速排序对包含一个元素的数组管用,对包含两 个元素的数组也将管用;如果它对包含两个元素的数组管用,对包含三个元素的数组也将管用, 以此类推。因此,我可以说,快速排序对任何长度的数组都管用。这里不再深入讨论归纳证明, 但它很有趣,并与D&C协同发挥作用 。
# 快排的python代码
def qsort(array):
	if len(array) < 2 :
		return array #基线条件:为空或者只有一个
	else:
		pivot = array[0]; # 递归条件
		less = [i for i in array[1:] if i <= pivot]
		greater = [i for i in array[1:] if i > pivot]
		return qsort(less) + [pivot] + qsort(greater)

print(qsort([10,5,2,3]))
  1. 还有一种名为 合并排序(merge sort) 的排序算法,其运行时间为O(nlog n),比选择排序快得多!快速排序的情况比较棘手,在最糟情况下,其运行时间为O(n^2)。 与选择排序一样慢!但这是最糟情况。在平均情况下,快速排序的运行时间为O(n log n)
    那么你可能就会问了:若快速排序在平均情况下的运行时间为O(nlog n),而合并排序的运行时间总是O(nlog n), 为何不使用合并排序?它不是更快吗。别急,下面我们就好好讨论一下这个问题。
    有时候,常量的影响可能很大,对快速查找和合并查找来说就是如此。快速查找的常量比合并查找小,因此如果它们的运行时间都为O(nlog n),快速查找的速度将更快。实际上,快速查找的速度确实更快,因为相对于遇上最糟情况,它遇上平均情况的可能性要大得多。例如:下图当数据量很大的时候,常量影响就无关紧要了。
    Summary--算法图解Summary--算法图解
    同理,对于快排,恰好选中最小的元素作为基准值的是最糟情况(调用栈非常长),而如果你总是将中间元素作为基准值则是最佳情况。在最糟情况下,栈长为 O(n),而在最佳情况下,栈长为O(log n)。在这个示例中,层数为O(log n)(用技术术语说,调用栈的高度为O(log n))而每层需要的 时间为O(n)。因此整个算法需要的时间为O(n) * O(log n) = O(n log n)。这就是最佳情况。 在最糟情况下,有O(n)层,因此该算法的运行时间为O(n) * O(n) = O(n^2)。 图解:
    Summary--算法图解

小小summary一下:

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