Python算法教程第三章知識(shí)點(diǎn)：求和式、遞歸式、侏儒排序法和并歸排序法

發(fā)布時(shí)間：2020-08-05 23:06:13 來源：網(wǎng)絡(luò) 閱讀：275 作者：qq5b6d5cea82940 欄目：編程語言

本文目錄：一、求和式；二、遞歸式；三、侏儒排序法和并歸排序法
微信公眾號(hào)：geekkr

一、求和式

# 假設(shè)有一函數(shù)為f()，則在Python中經(jīng)常使用的求和方法如下。

sum(f(i) for i in range(m, n+1)) + sum(g(i) for i in range(m, n+1))

sum(f(i)+g(i) for i in range(m, n+1))

二、遞歸式

# 舉個(gè)栗子

def S(seq, i=0):
    if i == len(seq): return 0
    return S(seq, i+1) + seq[i]

三、侏儒排序法和并歸排序法

# 侏儒排序法

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

侏儒排序法的運(yùn)行時(shí)間介于\Omega (n)\Omega (n^{2})之間；而并歸排序法的運(yùn)行時(shí)間為\theta (nlgn)。

向AI問一下細(xì)節(jié)

Python算法教程第三章知識(shí)點(diǎn)：求和式、遞歸式、侏儒排序法和并歸排序法

猜你喜歡

最新資訊

相關(guān)推薦

相關(guān)標(biāo)簽

Python算法教程第三章知識(shí)點(diǎn)：求和式、遞歸式、侏儒排序法和并歸排序法