国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

SICP Python 描述 3.2 函數(shù)和所生成的過(guò)程

lolomaco / 1710人閱讀

摘要:函數(shù)和所生成的過(guò)程來(lái)源譯者飛龍協(xié)議函數(shù)是計(jì)算過(guò)程的局部演化模式。在這一章中,我們會(huì)檢測(cè)一些用于簡(jiǎn)單函數(shù)所生成過(guò)程的通用模型。也就是說(shuō),遞歸函數(shù)的執(zhí)行過(guò)程可能需要再次調(diào)用這個(gè)函數(shù)。

3.2 函數(shù)和所生成的過(guò)程

來(lái)源:3.2 Functions and the Processes They Generate

譯者:飛龍

協(xié)議:CC BY-NC-SA 4.0

函數(shù)是計(jì)算過(guò)程的局部演化模式。它規(guī)定了過(guò)程的每個(gè)階段如何構(gòu)建在之前的階段之上。我們希望能夠創(chuàng)建有關(guān)過(guò)程整體行為的語(yǔ)句,而過(guò)程的局部演化由一個(gè)或多個(gè)函數(shù)指定。這種分析通常非常困難,但是我們至少可以試圖描述一些典型的過(guò)程演化模式。

在這一章中,我們會(huì)檢測(cè)一些用于簡(jiǎn)單函數(shù)所生成過(guò)程的通用“模型”。我們也會(huì)研究這些過(guò)程消耗重要的計(jì)算資源,例如時(shí)間和空間的比例。

3.2.1 遞歸函數(shù)

如果函數(shù)的函數(shù)體直接或者間接自己調(diào)用自己,那么這個(gè)函數(shù)是遞歸的。也就是說(shuō),遞歸函數(shù)的執(zhí)行過(guò)程可能需要再次調(diào)用這個(gè)函數(shù)。Python 中的遞歸函數(shù)不需要任何特殊的語(yǔ)法,但是它們的確需要一些注意來(lái)正確定義。

作為遞歸函數(shù)的介紹,我們以將英文單詞轉(zhuǎn)換為它的 Pig Latin 等價(jià)形式開(kāi)始。Pig Latin 是一種隱語(yǔ):對(duì)英文單詞使用一種簡(jiǎn)單、確定的轉(zhuǎn)換來(lái)掩蓋單詞的含義。Thomas Jefferson 據(jù)推測(cè)是先行者。英文單詞的 Pig Latin 等價(jià)形式將輔音前綴(可能為空)從開(kāi)頭移動(dòng)到末尾,并且添加-ay元音。所以,pun會(huì)變成unpaystout會(huì)變成outstayall會(huì)變成allay

>>> def pig_latin(w):
        """Return the Pig Latin equivalent of English word w."""
        if starts_with_a_vowel(w):
            return w + "ay"
        return pig_latin(w[1:] + w[0])
>>> def starts_with_a_vowel(w):
        """Return whether w begins with a vowel."""
        return w[0].lower() in "aeiou"

這個(gè)定義背后的想法是,一個(gè)以輔音開(kāi)頭的字符串的 Pig Latin 變體和另一個(gè)字符串的 Pig Latin 變體相同:它通過(guò)將第一個(gè)字母移到末尾來(lái)創(chuàng)建。于是,sending的 Pig Latin 變體就和endings的變體(endingsay)相同。smother的 Pig Latin 變體和mothers的變體(othersmay)相同。而且,將輔音從開(kāi)頭移動(dòng)到末尾會(huì)產(chǎn)生帶有更少輔音前綴的更簡(jiǎn)單的問(wèn)題。在sending的例子中,將s移動(dòng)到末尾會(huì)產(chǎn)生以元音開(kāi)頭的單詞,我們的任務(wù)就完成了。

即使pig_latin函數(shù)在它的函數(shù)體中調(diào)用,pig_latin的定義是完整且正確的。

>>> pig_latin("pun")
"unpay"

能夠基于函數(shù)自身來(lái)定義函數(shù)的想法可能十分令人混亂:“循環(huán)”定義如何有意義,這看起來(lái)不是很清楚,更不用說(shuō)讓計(jì)算機(jī)來(lái)執(zhí)行定義好的過(guò)程。但是,我們能夠準(zhǔn)確理解遞歸函數(shù)如何使用我們的計(jì)算環(huán)境模型來(lái)成功調(diào)用。環(huán)境的圖示和描述pig_latin("pun")求值的表達(dá)式樹(shù)展示在下面:

Python 求值過(guò)程的步驟產(chǎn)生如下結(jié)果:

pig_latin def語(yǔ)句 被執(zhí)行,其中:

使用函數(shù)體創(chuàng)建新的pig_latin函數(shù)對(duì)象,并且

將名稱pig_latin在當(dāng)前(全局)幀中綁定到這個(gè)函數(shù)上。

starts_with_a_vowel def語(yǔ)句類似地執(zhí)行。

求出pig_latin("pun")的調(diào)用表達(dá)式,通過(guò)

求出運(yùn)算符和操作數(shù)子表達(dá)式,通過(guò)

查找綁定到pig_latin函數(shù)的pig_latin名稱

對(duì)字符串對(duì)象"pun"求出操作數(shù)字符串字面值

在參數(shù)"pun"上調(diào)用pig_latin函數(shù),通過(guò)

添加擴(kuò)展自全局幀的局部幀

將形參w綁定到當(dāng)前幀的實(shí)參"pun"上。

在以當(dāng)前幀起始的環(huán)境中執(zhí)行pig_latin的函數(shù)體

最開(kāi)始的條件語(yǔ)句沒(méi)有效果,因?yàn)轭^部表達(dá)式求值為False

求出最后的返回表達(dá)式pig_latin(w[1:] + w[0]),通過(guò)

查找綁定到pig_latin函數(shù)的pig_latin名稱

對(duì)字符串對(duì)象"pun"求出操作數(shù)表達(dá)式

在參數(shù)"unp"上調(diào)用pig_latin,它會(huì)從pig_latin函數(shù)體中的條件語(yǔ)句組返回預(yù)期結(jié)果。

就像這個(gè)例子所展示的那樣,雖然遞歸函數(shù)具有循環(huán)特征,他仍舊正確調(diào)用。pig_latin函數(shù)調(diào)用了兩次,但是每次都帶有不同的參數(shù)。雖然第二個(gè)調(diào)用來(lái)自pig_latin自己的函數(shù)體,但由名稱查找函數(shù)會(huì)成功,因?yàn)槊Qpig_latin在它的函數(shù)體執(zhí)行前的環(huán)境中綁定。

這個(gè)例子也展示了 Python 的遞歸函數(shù)的求值過(guò)程如何與遞歸函數(shù)交互,來(lái)產(chǎn)生帶有許多嵌套步驟的復(fù)雜計(jì)算過(guò)程,即使函數(shù)定義本身可能包含非常少的代碼行數(shù)。

3.2.2 剖析遞歸函數(shù)

許多遞歸函數(shù)的函數(shù)體中都存在通用模式。函數(shù)體以基本條件開(kāi)始,它是一個(gè)條件語(yǔ)句,為需要處理的最簡(jiǎn)單的輸入定義函數(shù)行為。在pig_latin的例子中,基本條件對(duì)任何以元音開(kāi)頭的單詞成立。這個(gè)時(shí)候,只需要返回末尾附加ay的參數(shù)。一些遞歸函數(shù)會(huì)有多重基本條件。

基本條件之后是一個(gè)或多個(gè)遞歸調(diào)用。遞歸調(diào)用有特定的特征:它們必須簡(jiǎn)化原始問(wèn)題。在pig_latin的例子中,w中最開(kāi)始輔音越多,就需要越多的處理工作。在遞歸調(diào)用pig_latin(w[1:] + w[0])中,我們?cè)谝粋€(gè)具有更少初始輔音的單詞上調(diào)用pig_latin -- 這就是更簡(jiǎn)化的問(wèn)題。每個(gè)成功的pig_latin調(diào)用都會(huì)更加簡(jiǎn)化,直到滿足了基本條件:一個(gè)沒(méi)有初始輔音的單詞。

遞歸調(diào)用通過(guò)逐步簡(jiǎn)化問(wèn)題來(lái)表達(dá)計(jì)算。與我們?cè)谶^(guò)去使用過(guò)的迭代方式相比,它們通常以不同方式來(lái)解決問(wèn)題。考慮用于計(jì)算n的階乘的函數(shù)fact,其中fact(4)計(jì)算了4! = 4·3·2·1 = 24

使用while語(yǔ)句的自然實(shí)現(xiàn)會(huì)通過(guò)將每個(gè)截至n的正數(shù)相乘來(lái)求出結(jié)果。

>>> def fact_iter(n):
        total, k = 1, 1
        while k <= n:
            total, k = total * k, k + 1
        return total
>>> fact_iter(4)
24

另一方面,階乘的遞歸實(shí)現(xiàn)可以以fact(n-1)(一個(gè)更簡(jiǎn)單的問(wèn)題)來(lái)表示fact(n)。遞歸的基本條件是問(wèn)題的最簡(jiǎn)形式:fact(1)1

>>> def fact(n):
        if n == 1:
            return 1
        return n * fact(n-1)
>>> fact(4)
24

函數(shù)的正確性可以輕易通過(guò)階乘函數(shù)的標(biāo)準(zhǔn)數(shù)學(xué)定義來(lái)驗(yàn)證。

(n ? 1)! = (n ? 1)·(n ? 2)· ... · 1
n! = n·(n ? 1)·(n ? 2)· ... · 1
n! = n·(n ? 1)!  

這兩個(gè)階乘函數(shù)在概念上不同。迭代的函數(shù)通過(guò)將每個(gè)式子,從基本條件1到最終的總數(shù)逐步相乘來(lái)構(gòu)造結(jié)果。另一方面,遞歸函數(shù)直接從最終的式子n和簡(jiǎn)化的問(wèn)題fact(n-1)構(gòu)造結(jié)果。

fact函數(shù)應(yīng)用于更簡(jiǎn)單的問(wèn)題實(shí)例,來(lái)展開(kāi)遞歸的同時(shí),結(jié)果最終由基本條件構(gòu)建。下面的圖示展示了遞歸如何向fact傳入1而終止,以及每個(gè)調(diào)用的結(jié)果如何依賴于下一個(gè)調(diào)用,直到滿足了基本條件。

雖然我們可以使用我們的計(jì)算模型展開(kāi)遞歸,通常把遞歸調(diào)用看做函數(shù)抽象更清晰一些。也就是說(shuō),我們不應(yīng)該關(guān)心fact(n-1)如何在fact的函數(shù)體中實(shí)現(xiàn);我們只需要相信它計(jì)算了n-1的階乘。將遞歸調(diào)用看做函數(shù)抽象叫做遞歸的“信仰飛躍”(leap of faith)。我們以函數(shù)自身來(lái)定義函數(shù),但是僅僅相信更簡(jiǎn)單的情況在驗(yàn)證函數(shù)正確性時(shí)會(huì)正常工作。這個(gè)例子中我們相信,fact(n-1)會(huì)正確計(jì)算(n-1)!;我們只需要檢查,如果滿足假設(shè)n!是否正確計(jì)算。這樣,遞歸函數(shù)正確性的驗(yàn)證就變成了一種歸納證明。

函數(shù)fact_iterfact也不一樣,因?yàn)榍罢弑仨氁雰蓚€(gè)額外的名稱,totalk,它們?cè)谶f歸實(shí)現(xiàn)中并不需要。通常,迭代函數(shù)必須維護(hù)一些局部狀態(tài),它們會(huì)在計(jì)算過(guò)程中改變。在任何迭代的時(shí)間點(diǎn)上,狀態(tài)刻畫了已完成的結(jié)果,以及未完成的工作總量。例如,當(dāng)k3total2時(shí),就還剩下兩個(gè)式子沒(méi)有處理,34。另一方面,fact由單一參數(shù)n來(lái)刻畫。計(jì)算的狀態(tài)完全包含在表達(dá)式樹(shù)的結(jié)果中,它的返回值起到total的作用,并且在不同的幀中將n綁定到不同的值上,而不是顯式跟蹤k

遞歸函數(shù)可以更加依賴于解釋器本身,通過(guò)將計(jì)算狀態(tài)儲(chǔ)存為表達(dá)式樹(shù)和環(huán)境的一部分,而不是顯式使用局部幀中的名稱。出于這個(gè)原因,遞歸函數(shù)通常易于定義,因?yàn)槲覀儾恍枰囍灞仨氃诘芯S護(hù)的局部狀態(tài)。另一方面,學(xué)會(huì)弄清由遞歸函數(shù)實(shí)現(xiàn)的計(jì)算過(guò)程,需要一些練習(xí)。

3.2.3 樹(shù)形遞歸

另一個(gè)遞歸的普遍模式叫做樹(shù)形遞歸。例如,考慮斐波那契序列的計(jì)算,其中每個(gè)數(shù)值都是前兩個(gè)的和。

>>> def fib(n):
        if n == 1:
            return 0
        if n == 2:
            return 1
        return fib(n-2) + fib(n-1)
>>> fib(6)
5

這個(gè)遞歸定義和我們之前的嘗試有很大關(guān)系:它準(zhǔn)確反映了斐波那契數(shù)的相似定義。考慮求出fib(6)所產(chǎn)生的計(jì)算模式,它展示在下面。為了計(jì)算fib(6),我們需要計(jì)算fib(5)fib(4)。為了計(jì)算fib(5),我們需要計(jì)算fib(4)fib(3)。通常,這個(gè)演化過(guò)程看起來(lái)像一棵樹(shù)(下面的圖并不是完整的表達(dá)式樹(shù),而是簡(jiǎn)化的過(guò)程描述;一個(gè)完整的表達(dá)式樹(shù)也擁有同樣的結(jié)構(gòu))。在遍歷這棵樹(shù)的過(guò)程中,每個(gè)藍(lán)點(diǎn)都表示斐波那契數(shù)的已完成計(jì)算。

調(diào)用自身多次的函數(shù)叫做樹(shù)形遞歸。以樹(shù)形遞歸為原型編寫的函數(shù)十分有用,但是用于計(jì)算斐波那契數(shù)則非常糟糕,因?yàn)樗隽撕芏嘀貜?fù)的計(jì)算。要注意整個(gè)fib(4)的計(jì)算是重復(fù)的,它幾乎是一半的工作量。實(shí)際上,不難得出函數(shù)用于計(jì)算fib(1)fib(2)(通常是樹(shù)中的葉子數(shù)量)的時(shí)間是fib(n+1)。為了弄清楚這有多糟糕,我們可以證明fib(n)的值隨著n以指數(shù)方式增長(zhǎng)。所以,這個(gè)過(guò)程的步驟數(shù)量隨輸入以指數(shù)方式增長(zhǎng)。

我們已經(jīng)見(jiàn)過(guò)斐波那契數(shù)的迭代實(shí)現(xiàn),出于便利在這里貼出來(lái):

>>> def fib_iter(n):
        prev, curr = 1, 0  # curr is the first Fibonacci number.
        for _ in range(n-1):
             prev, curr = curr, prev + curr
        return curr

這里我們必須維護(hù)的狀態(tài)由當(dāng)前值和上一個(gè)斐波那契數(shù)組成。for語(yǔ)句也顯式跟蹤了迭代數(shù)量。這個(gè)定義并沒(méi)有像遞歸方式那樣清晰反映斐波那契數(shù)的數(shù)學(xué)定義。但是,迭代實(shí)現(xiàn)中所需的計(jì)算總數(shù)只是線性,而不是指數(shù)于n的。甚至對(duì)于n的較小值,這個(gè)差異都非常大。

然而我們不應(yīng)該從這個(gè)差異總結(jié)出,樹(shù)形遞歸的過(guò)程是沒(méi)有用的。當(dāng)我們考慮層次數(shù)據(jù)結(jié)構(gòu),而不是數(shù)值上的操作時(shí),我們發(fā)現(xiàn)樹(shù)形遞歸是自然而強(qiáng)大的工具。而且,樹(shù)形過(guò)程可以變得更高效。

記憶。用于提升重復(fù)計(jì)算的遞歸函數(shù)效率的機(jī)制叫做記憶。記憶函數(shù)會(huì)為任何之前接受的參數(shù)儲(chǔ)存返回值。fib(4)的第二次調(diào)用不會(huì)執(zhí)行與第一次同樣的復(fù)雜過(guò)程,而是直接返回第一次調(diào)用的已儲(chǔ)存結(jié)果。

記憶函數(shù)可以自然表達(dá)為高階函數(shù),也可以用作裝飾器。下面的定義為之前的已計(jì)算結(jié)果創(chuàng)建緩存,由被計(jì)算的參數(shù)索引。在這個(gè)實(shí)現(xiàn)中,這個(gè)字典的使用需要記憶函數(shù)的參數(shù)是不可變的。

>>> def memo(f):
        """Return a memoized version of single-argument function f."""
        cache = {}
        def memoized(n):
            if n not in cache:
                cache[n] = f(n)
            return cache[n]
        return memoized
>>> fib = memo(fib)
>>> fib(40)
63245986

由記憶函數(shù)節(jié)省的所需的計(jì)算時(shí)間總數(shù)在這個(gè)例子中是巨大的。被記憶的遞歸函數(shù)fib和迭代函數(shù)fib_iter都只需要線性于輸入n的時(shí)間總數(shù)。為了計(jì)算fib(40)fib的函數(shù)體只執(zhí)行 40 次,而不是無(wú)記憶遞歸中的 102,334,155 次。

空間。為了理解函數(shù)所需的空間,我們必須在我們的計(jì)算模型中規(guī)定內(nèi)存如何使用,保留和回收。在求解表達(dá)式過(guò)程中,我們必須保留所有活動(dòng)環(huán)境和所有這些環(huán)境引用的值和幀。如果環(huán)境為表達(dá)式樹(shù)當(dāng)前分支中的一些表達(dá)式提供求值上下文,那么它就是活動(dòng)環(huán)境。

例如,當(dāng)求值fib時(shí),解釋器按序計(jì)算之前的每個(gè)值,遍歷樹(shù)形結(jié)構(gòu)。為了這樣做,它只需要在計(jì)算的任何時(shí)間點(diǎn),跟蹤樹(shù)中在當(dāng)前節(jié)點(diǎn)之前的那些節(jié)點(diǎn)。用于求出剩余節(jié)點(diǎn)的內(nèi)存可以被回收,因?yàn)樗粫?huì)影響未來(lái)的計(jì)算。通常,樹(shù)形遞歸所需空間與樹(shù)的深度成正比。

下面的圖示描述了由求解fib(3)生成的表達(dá)式樹(shù)。在求解fib最初調(diào)用的返回表達(dá)式的過(guò)程中,fib(n-2)被求值,產(chǎn)生值0。一旦這個(gè)值計(jì)算出來(lái),對(duì)應(yīng)的環(huán)境幀(標(biāo)為灰色)就不再需要了:它并不是活動(dòng)環(huán)境的一部分。所以,一個(gè)設(shè)計(jì)良好的解釋器會(huì)回收用于儲(chǔ)存這個(gè)幀的內(nèi)存。另一方面,如果解釋器當(dāng)前正在求解fib(n-1),那么由這次fib調(diào)用(其中n2)創(chuàng)建的環(huán)境是活動(dòng)的。與之對(duì)應(yīng),最開(kāi)始在3上調(diào)用fib所創(chuàng)建的環(huán)境也是活動(dòng)的,因?yàn)檫@個(gè)值還沒(méi)有成功計(jì)算出來(lái)。

memo的例子中,只要一些名稱綁定到了活動(dòng)環(huán)境中的某個(gè)函數(shù)上,關(guān)聯(lián)到所返回函數(shù)(它包含cache)的環(huán)境必須保留。cache字典中的條目數(shù)量隨傳遞給fib的唯一參數(shù)數(shù)量線性增長(zhǎng),它的規(guī)模線性于輸入。另一方面,迭代實(shí)現(xiàn)只需要兩個(gè)數(shù)值來(lái)在計(jì)算過(guò)程中跟蹤:prevcurr,所以是常數(shù)大小。

我們使用記憶函數(shù)的例子展示了編程中的通用模式,即通常可以通過(guò)增加所用空間來(lái)減少計(jì)算時(shí)間,反之亦然。

3.2.4 示例:找零

考慮下面這個(gè)問(wèn)題:如果給你半美元、四分之一美元、十美分、五美分和一美分,一美元有多少種找零的方式?更通常來(lái)說(shuō),我們能不能編寫一個(gè)函數(shù),使用一系列貨幣的面額,計(jì)算有多少種方式為給定的金額總數(shù)找零?

這個(gè)問(wèn)題可以用遞歸函數(shù)簡(jiǎn)單解決。假設(shè)我們認(rèn)為可用的硬幣類型以某種順序排列,假設(shè)從大到小排列。

使用n種硬幣找零的方式為:

使用所有除了第一種之外的硬幣為a找零的方式,以及

使用n種硬幣為更小的金額a - d找零的方式,其中d是第一種硬幣的面額。

為了弄清楚為什么這是正確的,可以看出,找零方式可以分為兩組,不使用第一種硬幣的方式,和使用它們的方式。所以,找零方式的總數(shù)等于不使用第一種硬幣為該金額找零的方式數(shù)量,加上使用第一種硬幣至少一次的方式數(shù)量。而后者的數(shù)量等于在使用第一種硬幣之后,為剩余的金額找零的方式數(shù)量。

因此,我們可以遞歸將給定金額的找零問(wèn)題,歸約為使用更少種類的硬幣為更小的金額找零的問(wèn)題。仔細(xì)考慮這個(gè)歸約原則,并且說(shuō)服自己,如果我們規(guī)定了下列基本條件,我們就可以使用它來(lái)描述算法:

如果a正好是零,那么有一種找零方式。

如果a小于零,那么有零種找零方式。

如果n小于零,那么有零種找零方式。

我們可以輕易將這個(gè)描述翻譯成遞歸函數(shù):

>>> def count_change(a, kinds=(50, 25, 10, 5, 1)):
        """Return the number of ways to change amount a using coin kinds."""
        if a == 0:
            return 1
        if a < 0 or len(kinds) == 0:
            return 0
        d = kinds[0]
        return count_change(a, kinds[1:]) + count_change(a - d, kinds)
>>> count_change(100)
292

count_change函數(shù)生成樹(shù)形遞歸過(guò)程,和fib的首個(gè)實(shí)現(xiàn)一樣,它是重復(fù)的。它會(huì)花費(fèi)很長(zhǎng)時(shí)間來(lái)計(jì)算出292,除非我們記憶這個(gè)函數(shù)。另一方面,設(shè)計(jì)迭代算法來(lái)計(jì)算出結(jié)果的方式并不是那么明顯,我們將它留做一個(gè)挑戰(zhàn)。

3.2.5 增長(zhǎng)度

前面的例子表明,不同過(guò)程在花費(fèi)的時(shí)間和空間計(jì)算資源上有顯著差異。我們用于描述這個(gè)差異的便捷方式,就是使用增長(zhǎng)度的概念,來(lái)獲得當(dāng)輸入變得更大時(shí),過(guò)程所需資源的大致度量。

n為度量問(wèn)題規(guī)模的參數(shù),R(n)為處理規(guī)模為n的問(wèn)題的過(guò)程所需的資源總數(shù)。在我們前面的例子中,我們將n看做給定函數(shù)所要計(jì)算出的數(shù)值。但是還有其他可能。例如,如果我們的目標(biāo)是計(jì)算某個(gè)數(shù)值的平方根近似值,我們會(huì)將n看做所需的有效位數(shù)的數(shù)量。通常,有一些問(wèn)題相關(guān)的特性可用于分析給定的過(guò)程。與之相似,R(n)可用于度量所用的內(nèi)存總數(shù),所執(zhí)行的基本的機(jī)器操作數(shù)量,以及其它。在一次只執(zhí)行固定數(shù)量操作的計(jì)算中,用于求解表達(dá)式的所需時(shí)間,與求值過(guò)程中執(zhí)行的基本機(jī)器操作數(shù)量成正比。

我們說(shuō),R(n)具有Θ(f(n))的增長(zhǎng)度,寫作R(n)=Θ(f(n))(讀作“theta f(n)”),如果存在獨(dú)立于n的常數(shù)k1k2,那么對(duì)于任何足夠大的n值:

k1·f(n) <= R(n) <= k2·f(n)

也就是說(shuō),對(duì)于較大的nR(n)的值夾在兩個(gè)具有f(n)規(guī)模的值之間:

下界k1·f(n),以及

上界k2·f(n)

例如,計(jì)算n!所需的步驟數(shù)量與n成正比,所以這個(gè)過(guò)程的所需步驟以Θ(n)增長(zhǎng)。我們也看到了,遞歸實(shí)現(xiàn)fact的所需空間以Θ(n)增長(zhǎng)。與之相反,迭代實(shí)現(xiàn)fact_iter 花費(fèi)相似的步驟數(shù)量,但是所需的空間保持不變。這里,我們說(shuō)這個(gè)空間以Θ(1)增長(zhǎng)。

我們的樹(shù)形遞歸的斐波那契數(shù)計(jì)算函數(shù)fib 的步驟數(shù)量,隨輸入n指數(shù)增長(zhǎng)。尤其是,我們可以發(fā)現(xiàn),第 n 個(gè)斐波那契數(shù)是距離φ^(n-2)/√5的最近整數(shù),其中φ是黃金比例:

φ = (1 + √5)/2 ≈ 1.6180

我們也表示,步驟數(shù)量隨返回值增長(zhǎng)而增長(zhǎng),所以樹(shù)形遞歸過(guò)程需要Θ(φ^n)的步驟,它的一個(gè)隨n指數(shù)增長(zhǎng)的函數(shù)。

增長(zhǎng)度只提供了過(guò)程行為的大致描述。例如,需要n^2個(gè)步驟的過(guò)程和需要1000·n^2個(gè)步驟的過(guò)程,以及需要3·n^2+10·n+17個(gè)步驟的過(guò)程都擁有Θ(n^2)的增長(zhǎng)度。在特定的情況下,增長(zhǎng)度的分析過(guò)于粗略,不能在函數(shù)的兩個(gè)可能實(shí)現(xiàn)中做出判斷。

但是,增長(zhǎng)度提供了實(shí)用的方法,來(lái)表示在改變問(wèn)題規(guī)模的時(shí)候,我們應(yīng)如何預(yù)期過(guò)程行為的改變。對(duì)于Θ(n)(線性)的過(guò)程,使規(guī)模加倍只會(huì)使所需的資源總數(shù)加倍。對(duì)于指數(shù)的過(guò)程,每一點(diǎn)問(wèn)題規(guī)模的增長(zhǎng)都會(huì)使所用資源以固定因數(shù)翻倍。接下來(lái)的例子展示了一個(gè)增長(zhǎng)度為對(duì)數(shù)的算法,所以使問(wèn)題規(guī)模加倍,只會(huì)使所需資源以固定總數(shù)增加。

3.2.6 示例:求冪

考慮對(duì)給定數(shù)值求冪的問(wèn)題。我們希望有一個(gè)函數(shù),它接受底數(shù)b和正整數(shù)指數(shù)n作為參數(shù),并計(jì)算出b^n。一種方式就是通過(guò)遞歸定義:

b^n = b·b^(n-1)
b^0 = 1

這可以翻譯成遞歸函數(shù):

>>> def exp(b, n):
        if n == 0:
            return 1
        return b * exp(b, n-1)

這是個(gè)線性的遞歸過(guò)程,需要Θ(n)的步驟和空間。就像階乘那樣,我們可以編寫等價(jià)的線性迭代形式,它需要相似的步驟數(shù)量,但只需要固定的空間。

>>> def exp_iter(b, n):
        result = 1
        for _ in range(n):
            result = result * b
        return result

我們可以以更少的步驟求冪,通過(guò)逐次平方。例如,我們這樣計(jì)算b^8

b·(b·(b·(b·(b·(b·(b·b))))))

我們可以使用三次乘法來(lái)計(jì)算它:

b^2 = b·b
b^4 = b^2·b^2
b^8 = b^4·b^4

這個(gè)方法對(duì)于 2 的冪的指數(shù)工作良好。我們也可以使用這個(gè)遞歸規(guī)則,在求冪中利用逐步平方的優(yōu)點(diǎn):

我們同樣可以將這個(gè)方式表達(dá)為遞歸函數(shù):

>>> def square(x):
        return x*x
>>> def fast_exp(b, n):
        if n == 0:
            return 1
        if n % 2 == 0:
            return square(fast_exp(b, n//2))
        else:
            return b * fast_exp(b, n-1)
>>> fast_exp(2, 100)
1267650600228229401496703205376

fast_exp所生成的過(guò)程的空間和步驟數(shù)量隨n以對(duì)數(shù)方式增長(zhǎng)。為了弄清楚它,可以看出,使用fast_exp計(jì)算b^2n比計(jì)算b^n只需要一步額外的乘法操作。于是,我們能夠計(jì)算的指數(shù)大小,在每次新的乘法操作時(shí)都會(huì)(近似)加倍。所以,計(jì)算n的指數(shù)所需乘法操作的數(shù)量,增長(zhǎng)得像以2為底n的對(duì)數(shù)那樣慢。這個(gè)過(guò)程擁有Θ(log n)的增長(zhǎng)度。Θ(log n)Θ(n)之間的差異在n非常大時(shí)變得顯著。例如,n1000時(shí),fast_exp 僅僅需要14個(gè)乘法操作,而不是1000

文章版權(quán)歸作者所有,未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址:http://specialneedsforspecialkids.com/yun/38152.html

相關(guān)文章

  • SICP Python描述 1.1 引言

    摘要:另一個(gè)賦值語(yǔ)句將名稱關(guān)聯(lián)到出現(xiàn)在莎士比亞劇本中的所有去重詞匯的集合,總計(jì)個(gè)。表達(dá)式是一個(gè)復(fù)合表達(dá)式,計(jì)算出正序或倒序出現(xiàn)的莎士比亞詞匯集合。在意圖上并沒(méi)有按照莎士比亞或者回文來(lái)設(shè)計(jì),但是它極大的靈活性讓我們用極少的代碼處理大量文本。 1.1 引言 來(lái)源:1.1 Introduction 譯者:飛龍 協(xié)議:CC BY-NC-SA 4.0 計(jì)算機(jī)科學(xué)是一個(gè)極其寬泛的學(xué)科。全球的分布...

    xumenger 評(píng)論0 收藏0
  • SICP Python 描述 3.3 遞歸數(shù)據(jù)結(jié)構(gòu)

    摘要:遞歸列表可以使用遞歸函數(shù)最為自然地操作,就像它們的名稱和結(jié)構(gòu)表示的那樣。處理遞歸列表遞歸列表結(jié)構(gòu)將列表表示為首個(gè)元素和列表的剩余部分的組合。例如,我們可以使用高階遞歸函數(shù)將樹(shù)的每個(gè)葉子平方,它的結(jié)構(gòu)類似于。成員測(cè)試會(huì)遞歸遍歷整個(gè)列表。 3.3 遞歸數(shù)據(jù)結(jié)構(gòu) 來(lái)源:3.3 Recursive Data Structures 譯者:飛龍 協(xié)議:CC BY-NC-SA 4.0 在第二...

    libin19890520 評(píng)論0 收藏0
  • SICP Python 描述 第三章 計(jì)算機(jī)程序構(gòu)造和解釋 3.1 引言

    摘要:為通用語(yǔ)言設(shè)計(jì)解釋器的想法可能令人畏懼。但是,典型的解釋器擁有簡(jiǎn)潔的通用結(jié)構(gòu)兩個(gè)可變的遞歸函數(shù),第一個(gè)求解環(huán)境中的表達(dá)式,第二個(gè)在參數(shù)上調(diào)用函數(shù)。這一章接下來(lái)的兩節(jié)專注于遞歸函數(shù)和數(shù)據(jù)結(jié)構(gòu),它們是理解解釋器設(shè)計(jì)的基礎(chǔ)。 3.1 引言 來(lái)源:3.1 Introduction 譯者:飛龍 協(xié)議:CC BY-NC-SA 4.0 第一章和第二章描述了編程的兩個(gè)基本元素:數(shù)據(jù)和函數(shù)之間的...

    v1 評(píng)論0 收藏0
  • SICP Python 描述 1.2 編程元素

    摘要:程序用于在編程社群的成員之間交流這些想法。在編程中,我們處理兩種元素函數(shù)和數(shù)據(jù)。在中,我們可以使用賦值語(yǔ)句來(lái)建立新的綁定,它包含左邊的名稱和右邊的值。例如,它并不能處理賦值語(yǔ)句。這些圖解的必要部分是函數(shù)的表示。 1.2 編程元素 來(lái)源:1.2 The Elements of Programming 譯者:飛龍 協(xié)議:CC BY-NC-SA 4.0 編程語(yǔ)言是操作計(jì)算機(jī)來(lái)執(zhí)行任務(wù)...

    CoorChice 評(píng)論0 收藏0
  • SICP Python 描述 第二章 使用對(duì)象構(gòu)建抽象 2.1 引言

    摘要:對(duì)象表示信息,但是同時(shí)和它們所表示的抽象概念行為一致。通過(guò)綁定行為和信息,對(duì)象提供了可靠獨(dú)立的日期抽象。名稱來(lái)源于實(shí)數(shù)在中表示的方式浮點(diǎn)表示。另一方面,對(duì)象可以表示很大范圍內(nèi)的分?jǐn)?shù),但是不能表示所有有理數(shù)。 2.1 引言 來(lái)源:2.1 Introduction 譯者:飛龍 協(xié)議:CC BY-NC-SA 4.0 在第一章中,我們專注于計(jì)算過(guò)程,以及程序設(shè)計(jì)中函數(shù)的作用。我們看到了...

    phoenixsky 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

lolomaco

|高級(jí)講師

TA的文章

閱讀更多
最新活動(dòng)
閱讀需要支付1元查看
<