Python Algorithms – chapter3 计数初步,algorit

2019-12-17 作者:计算机教程   |   浏览(51)

Python Algorithms – chapter3 计数初步,algorithmschapter3

一些基本递归式的解决方案及其应用实例

主定理的三种情况

排序算法之侏儒排序法

def gnomesort(seq):
    i = 0
    while i < len(seq):
        if i == 0 or seq[i-1] <= seq[i]:
            i  = 1
        else:
            seq[i], seq[i-1] = seq[i-1], seq[i]
            i -= 1

排序算法之归并排序法

def mergesort(seq):
    mid = len(seq)/2
    lft, rgt = seq[:mid], seq[mid:]
    if len(lft) > 1: lft = mergesort(lft)
    if len(rgt) > 1: rgt = mergesort(rgt)
    res = []
    while lft and rgt:
        if lft[-1] >= rgt[-1]:
            res.append(lft.pop())
        else:
            res.append(rgt.pop())
        res.reverse()
        return (lft or rgt)   res

http://www.bkjia.com/Pythonjc/1304182.htmlwww.bkjia.comtruehttp://www.bkjia.com/Pythonjc/1304182.htmlTechArticlePython Algorithms chapter3 计数初步,algorithmschapter3 一些基本递归式的解决方案及其应用实例 主定理的三种情况 排序算法之侏儒排序法 def gnom...

案例2:

T(n) = T(2n/3) 1
其中,a = 1, b = 3/2, f(n) = 1,因此 nlogba = nlog3/21 = n0 = 1 。由于 f(n) = Θ(1) ,与Θ(nlogba)恰好相等,可应用于情况2,从而得到解 T(n) = Θ(lgn) 。

分治法

1.Divide
2.Conquer
3.combine

递归树法(之前出现的归并算法中已经用到)

www.2003.com 1

Example

定理4.1(主定理) 令 a≥1 和 b>1 是常数,f(n) 是一个函数,T(n) 是定义在非负整数上的递归式:
T(n) = aT(n/b) f(n)
那么T(n)有如下渐进界:
1.若对某个常数 ε>0 有 f(n) = O(nlogba-ε),则 T(n) = Θ(nlogba) 。
2.若 f(n) = Θ(nlogba),则 T(n) = Θ(nlogba lgn) 。
3.若对某个常数 ε>0 有 f(n) = Ω(nlogba ε),且对某个常数 c<1 和所有足够大的 n 有 af(n/b) ≤ cf(n),则 T(n) = Θ(f(n)) 。

Insert—Sort(A,n) 伪代码

for j<—2 to n
    do key<— A[j]
    i<—j-1
    while(i > 0 and A[i] > key)
        do A[i 1] <—A[i]
            i<—i-1
    A[i 1] <—key

strassen矩阵算法

www.2003.com 2

strassen

乘方问题&Fibonacci

www.2003.com 3

乘方&Fibonacci

性能就好像是平常的货币一样,我们用它交换安全和性能。

案例1:

T(n) = 9T(n/3) n
对于这个递归式,我们有 a = 9,b = 3, f(n) = n,因此 nlogba = nlog39 = Θ(n2) 。而 f(n) = n 渐进小于 Θ(n2),所以可以应用于主定理的情况1,从而得到解 T(n) = Θ(n2) 。

Example

T(n) = 4T(n/4) n
Guess T(n) = O(n³)
T(k) <= ck³

T(n) =  4T(n/2)    n
       ≤ 4(n/2)³   n
       = 1/2cn³   n
       = cn³ -(1/2cn³-n)

在c≥1 and n≥1 的情况下(1/2cn³-n)恒大于0
所以假设成立T(n) = O(n³)

Quick-Sort

快速排序的特点
www.2003.com,-Divide and conquer
-Sorts in place
-Very practical

www.2003.com 4

基本思路

www.2003.com 5

例子

j向右边移动,如果遇到比6大的数字则继续像右移动,如果遇到比6小的数字,将该数字与i 1下标数组数字交换,最后交换a[i]和一开始的参照数。

本文由www.2003.com发布于计算机教程,转载请注明出处:Python Algorithms &amp;ndash; chapter3 计数初步,algorit

关键词: