推进网站集约化建设 网络安全,网站下载的app删除了怎么找到,如何做地图的ppt模板下载网站,曲阜公司网站建设价格便宜1 引言
如题目所示#xff0c;本节的精华在于用数学解决一个直觉上看似纷乱复杂的问题#xff0c;里面有一些一般性的分析方法#xff0c;如引入Indicator变量#xff0c;从而把不确定问题引入到概率框架进行分析#xff0c;一步一步把直觉上混乱的问题理清楚#xff0c…1 引言
如题目所示本节的精华在于用数学解决一个直觉上看似纷乱复杂的问题里面有一些一般性的分析方法如引入Indicator变量从而把不确定问题引入到概率框架进行分析一步一步把直觉上混乱的问题理清楚数学之美也就是如此吧
如果有个算法在某些情况下表现的很差在某些情况下又表现的不错那么你还会放心的使用该算法吗通过下面的分析后你会很放心使用快速排序算法。
2 Quicksort
2.1 算法描述 2.2 手工演示
指针iii指示的是≤pivot\leq pivot≤pivot的最后一个作用是是用来标记≤pivot\leq pivot≤pivot和≥pivot\geq pivot≥pivot的分割状态指针jjj用来遍历所有元素每遍历一个元素都会和pivotpivotpivot比较不断更新iii的指示状态。
2.3 实现
# -*- coding: utf-8 -*-def PARTITION(A, p, r):x A[r]i p - 1for j in range(p, r):if A[j] x:i i 1A[i], A[j] A[j], A[i]A[i 1], A[r] A[r], A[i 1]return i 1def QUICK_SORT(A, p, r):if p r:q PARTITION(A, p, r)QUICK_SORT(A, p, q - 1)QUICK_SORT(A, q 1, r)if __name__ __main__:A [x, 2, 8, 7, 1, 3, 5, 6, 4]print(before sort:, A[1:])QUICK_SORT(A, 1, len(A) - 1)print(after sort:, A[1:])运行结果
before sort: [2, 8, 7, 1, 3, 5, 6, 4]
after sort: [1, 2, 3, 4, 5, 6, 7, 8]3 Analysis of quicksort
3.1 worst case 用递归树分析如下
3.2 best case 应用主定理容易得到T(n)Θ(nlogn)T(n)\Theta(nlogn)T(n)Θ(nlogn)。
3.3 110,910\frac{1}{10}, \frac{9}{10}101,109case
下面看一种感觉直觉上很差其实效果很好的情况。 使用递归树分析
注意log109n/log2nlog1092log_{\frac{10}{9}}n/log_{2}n log_{\frac{10}{9}}2log910n/log2nlog9102这是一个常数。
3.4 worst best交替情况 好坏交替的情况下最后仍然是好的
3.5 random case
上面从矛盾的特殊性上让直觉有一个直观的感受只要不是特别极端如一个初始状态是逆序的数列貌似大部分情况下都是ok的下面用概率框架确认这种直观的感觉是正确的。 对于离散不确定问题要引入概率框架进行讨论首先要引入一个合适的随机变量这里引入指示器Indicator随机变量这个变量在机器学习算法中使用更为广泛看似简单的一个定义却可以化繁为简的用一个表达式表示所有情况。 至此已经进入到概率框架可以暂时忘记之前的算法问题背景 概率世界都是是不确定的研究概率大目的是找出不确定问题的平均特性如期望、方差等这里只关注期望。 下面的推到中用到了期望的线性可加性和独立可乘性。 分割的独立性第一次分割后数组分为第a部分和第b部分a部分具体在哪个位置分割已经和第一次分割没有关系。 猜想E[T(n)]≤anlgnE[T(n)] ≤ an lg nE[T(n)]≤anlgna足够大接下来数学归纳法要登场了首先有一个数学事实要知道这个结论也是用数学归纳法容易证明 使用数学归纳法证明E[T(n)]≤anlgnE[T(n)] ≤ an lg nE[T(n)]≤anlgn
4 总结
从上面的分析中可以看到快速排序大概率是Θ(nlogn)\Theta(nlogn)Θ(nlogn)的在实际应用中快速排序往往是归并排序速度的2倍以上如果在细节上对算法微调则可以表现出更好的性能.
