遞階式創(chuàng)新思維培養(yǎng)在算法設(shè)計(jì)與分析課程中的應(yīng)用

摘要：文章以算法設(shè)計(jì)與分析課程中的選擇問題為例，探討遞階式創(chuàng)新思維的培養(yǎng)方法。通過引導(dǎo)學(xué)生逐步優(yōu)化選擇問題的解決方案，從簡單的排序算法到快速選擇算法，再到優(yōu)化基準(zhǔn)值的快速選擇算法，展現(xiàn)了遞階式創(chuàng)新思維在算法學(xué)習(xí)中的應(yīng)用。該方法鼓勵學(xué)生主動思考、發(fā)現(xiàn)問題、并逐步改進(jìn)解決方案，有效提升了學(xué)生的創(chuàng)新思維能力和問題解決能力。

關(guān)鍵詞：遞階式創(chuàng)新思維；算法分析；算法優(yōu)化；選擇問題

中圖分類號：G642" " " 文獻(xiàn)標(biāo)識碼：A

文章編號：1009-3044（2025）21-0038-03

開放科學(xué)（資源服務(wù)） 標(biāo)識碼（OSID）

0 引言

算法設(shè)計(jì)與分析（以下簡稱算法） 是計(jì)算機(jī)本科相關(guān)專業(yè)的核心專業(yè)課程，對培養(yǎng)學(xué)生分析、解決問題以及創(chuàng)新思維能力具有重要作用[1-4]。

我國著名教育家陶行知說過：“創(chuàng)造始于問題，有了問題才會思考，有了思考，才有解決問題的方法，才有找到獨(dú)立思路的可能”[5]。提出問題是創(chuàng)新的起點(diǎn)，只有學(xué)生學(xué)會提出問題，他們才能夠從不同的角度思考和探索，尋找新的解決方案。這種創(chuàng)造性的思維過程對于培養(yǎng)學(xué)生的創(chuàng)新意識和能力至關(guān)重要[6-7]。然而，目前的算法教學(xué)中對于“提出問題”這一環(huán)節(jié)關(guān)注不足，往往側(cè)重講解經(jīng)典問題的算法設(shè)計(jì)策略，學(xué)生被動接受知識，缺乏主動發(fā)現(xiàn)和提出問題的機(jī)會，不利于創(chuàng)新思維的培養(yǎng)。

因此，本研究旨在探討如何在算法教學(xué)中培養(yǎng)學(xué)生提出問題的能力，引導(dǎo)并鼓勵他們思考問題的局限性與改進(jìn)空間，并通過不斷提出新問題、分析和優(yōu)化解決方案，逐步提升解決問題的能力。本研究將以選擇問題為例，詳細(xì)闡述如何引導(dǎo)學(xué)生從提出問題到研究問題、再到優(yōu)化解決方案的過程，激發(fā)學(xué)生探索精神，推動他們在“提出問題—研究問題—解決問題”的迭代循環(huán)中實(shí)現(xiàn)遞階式創(chuàng)新思維的培養(yǎng)。

1 選擇問題描述

選擇問題（Selection Problem） （又稱為第k小查找問題） 本身簡單易懂，初步的解決方案容易給出，但卻隱含著深層次的算法優(yōu)化空間。因此，本研究選擇問題作為具體實(shí)例。

選擇問題可描述為：給定線性序集S中n個元素和一個整數(shù)k，1≤k≤n，要求找出這n個元素中第k小的元素。

進(jìn)一步解讀該問題：當(dāng)k=1時，即求最小值；k=n時，即求最大值；特別地當(dāng)[k=n/2]時，即求中位數(shù)，這是一類用以描述數(shù)據(jù)分布的統(tǒng)計(jì)量。

舉例：S={3，4，8，2，5，9，18}，若k=4，則解為5。

2 初步思路—排序算法求解

在授課過程中，通過問題驅(qū)動的方式，引導(dǎo)學(xué)生思考并探索解決問題的方法。

問題1：如何求解第k小的元素？

多數(shù)學(xué)生給出的直接思路都是通過排序求解該問題，具體過程可描述為：

1） 對集合S中n個元素進(jìn)行排序；

2） 直接找出n個元素中任意一個第k小的元素。

問題2：常見的排序算法有哪些？算法效率如何？

接下來可以和學(xué)生回顧常見的排序算法和算法效率分析。常見的排序算法包括快速排序、歸并排序、選擇排序、冒泡排序等，其平均時間復(fù)雜度均為O（nlogn）。而在一個有序數(shù)組中選擇第k小元素的時間復(fù)雜度為O（1）。因此，利用排序算法求解選擇問題的時間復(fù)雜度顯然為O（nlogn）。

問題3：引導(dǎo)思考——?dú)㈦u焉用牛刀？有必要獲得所有元素的次序嗎？

在分析排序算法求解選擇問題的時間復(fù)雜度后，還應(yīng)引導(dǎo)學(xué)生進(jìn)一步思考。通過對集合S排序，確實(shí)能獲得所有元素的次序信息。但思考一下，問題僅要求找出第k小的元素，而排序后可得到所有元素的次序，這是否有必要呢？此時，可以引導(dǎo)學(xué)生思考是否存在更高效的解決方案，能否在不完全排序的情況下快速找到第k小的元素。這樣的思考轉(zhuǎn)變，有助于激發(fā)學(xué)生深入思考問題本質(zhì)，探索更優(yōu)算法的興趣。

3 基于劃分思想—快速選擇

3.1 回顧快速排序

在引導(dǎo)學(xué)生思考更優(yōu)的算法實(shí)現(xiàn)方案之前，可以通過回顧快速排序算法，通過分析快速排序的實(shí)現(xiàn)過程，啟發(fā)學(xué)生進(jìn)一步的思考。

快速排序的基本實(shí)現(xiàn)步驟如下：

1） 劃分：選取一個基準(zhǔn)值p，將集合S劃分為兩個子集S1和S2，其中S1中的元素小于或等于p，S2中的元素大于或等于p。

2） 治理：遞歸地對子集S1和S2進(jìn)行快速排序。

3） 合并：無須額外操作，因?yàn)樵匾雅判颉?/p>

問題1：引導(dǎo)思考—如何在劃分后快速找到第k小元素？

在分析了快速排序的實(shí)現(xiàn)過程后，可以將注意力放在 “劃分（partition） ”思想上。通過劃分，得到了以基準(zhǔn)元素為界限的兩個子集。接下來，該如何在這兩個子集中找到第k小元素呢？可以進(jìn)一步思考：既然劃分操作本身已經(jīng)將元素分為兩部分，能否可以通過進(jìn)一步的分析，避免完全排序的過程，高效地定位到目標(biāo)元素？

小組討論：設(shè)計(jì)高效求解方案

課堂上，學(xué)生可以分組討論，思考如何基于劃分思想優(yōu)化算法。通過這種方式，學(xué)生能夠從中獲得新的設(shè)計(jì)思路，提出更高效的優(yōu)化解決方案。

3.2 快速選擇算法及效率分析

接下來，將快速排序中劃分的思想應(yīng)用于選擇問題的優(yōu)化解決方案中，這種算法被稱為“快速選擇”算法，其算法過程描述如下：

算法QuickSleclect （S， k）

輸入：包含n個元素的集合S和正整數(shù)k

輸出：S中的第k小元素

1） 選擇基準(zhǔn)值m對S進(jìn)行劃分。

該過程與快速排序中的劃分過程相同。選擇基準(zhǔn)值m，將集合S劃分為兩個子集S1和S2，其中S1中元素不大于m，S2中元素不小于m。設(shè)S1中的元素個數(shù)是|S1|， S2中的元素個數(shù)是|S2|。

2） 遞歸求解選擇問題。

若k=|S1| +1，則m為所求，直接返回m的值。

若k＜|S1|+1，第k小的元素應(yīng)在S1中，遞歸求解S1中的第k小元素。

若k＞|S1|+1，第k小的元素應(yīng)在S2中，遞歸求解S2中的第（k- |S1|-1）小元素。

接下來，對快速選擇算法進(jìn)行效率分析。與快速排序的效率分析相似，根據(jù)基準(zhǔn)值m所劃分位置的不同，快速選擇的效率可分為三種情況討論：

1） 最好情況：每次劃分恰好都位于集合的中點(diǎn)，其遞推方程如公式（1） 所示：

[T（n）=T（n/2）+O（n）]" " "（1）

最終可求得T（n）=O（n）。

2） 最壞情況：所有的劃分點(diǎn)都趨于極端，劃分后兩個子問題的規(guī)模一個為0，另一個是n-1，其遞推方程如公式（2） 所示：

[Tn=Tn-1+On]" " " " "（2）

最終求得[Tn=O（n2）]。

3） 平均情況：劃分點(diǎn)可能位于任意位置，每個位置的概率為1/n。與快速排序效率分析的平均情況相似，不同的在于只考慮其中較大的子問題，其遞推方程如公式（3） 所示：

[Tn≤maxT0，Tn-1+OnmaxT1，Tn-2+OnmaxT2， Tn-3+O（n）……maxTn-1，T0+On]" （3）

經(jīng)過分析，最終可求得[T（n）=O（n）]。

3.3 快速選擇與快速排序比較

為了幫助學(xué)生更好地理解快速選擇算法，可以將其與快速排序的算法效率進(jìn)行比較，如表1所示。引導(dǎo)學(xué)生思考兩者效率差異的原因：兩者的第一步都是劃分，但在劃分后，快速排序遞歸處理兩個子問題，而快速選擇只遞歸處理其中的一個子問題，少了一次遞歸調(diào)用。因此，平均情況下快速選擇的效率為O（n），高于快速排序。然而，最壞情況下，兩者的效率均是O（n2）。仔細(xì)分析一下不難發(fā)現(xiàn)，兩者的最壞情況均發(fā)生在極端劃分時，也即其中的一個子集為空。在此情況下，快速選擇并沒有真的節(jié)省一次遞歸調(diào)用，因此兩者的最壞情況時間復(fù)雜度是相同的。

4 優(yōu)化基準(zhǔn)值的快速選擇—最壞情況下的線性效率

4.1 引導(dǎo)思考：如何避免極端劃分

盡管快速選擇是解決選擇問題的優(yōu)化算法，但其最壞情況下時間復(fù)雜度仍然可能退化為O（n2），這是由于極端劃分所導(dǎo)致的。那么，是否有辦法能夠避免極端劃分，保證每次劃分都是“好”劃分呢？

答案是肯定的。最壞情況通常是由于“壞”的基準(zhǔn)值導(dǎo)致極端劃分。為了提高算法的最壞情況效率，關(guān)鍵在于如何選擇一個“好”的基準(zhǔn)值，避免極端劃分。雖然隨機(jī)選取基準(zhǔn)值能夠顯著降低最壞情況出現(xiàn)的概率，但無法完全避免最壞情況的發(fā)生。為此，需要找到一種方法，確保每次劃分都能避免極端情況。

這里，考慮一個理想的情形：每次選擇的基準(zhǔn)值都是集合的中位數(shù)，這樣每一次的劃分都恰好將問題規(guī)模減半，將集合劃分為兩個大小相等的子集，從而避免極端劃分的風(fēng)險。這種情況下算法時間復(fù)雜度如公式（4） 所示：

[Tn=n+n2+n4+...+n2logn-1+n2logn+1]" （4）

最終可求得T（n）=O（n），即線性時間復(fù)雜度。因此，若是選擇的基準(zhǔn)值盡可能地接近中位數(shù)，就可以保證算法效率為O（n）。

4.2 選擇更好的基準(zhǔn)值

選擇更好的基準(zhǔn)值以避免極端劃分的算法較復(fù)雜，具體過程如下[8]：

算法 Optimized Select（S， k）

輸入：n個數(shù)的集合S和正整數(shù)k。

輸出：S中的第k小元素。

①將S劃分成5個一組，共[n/5]組

②每組內(nèi)部按照從大到小的次序排序，取每組的中位數(shù)放到集合M中

③ m*←Optimized Select （M，[|M|/2]）

④用m*將S中的元素劃分為4個子集A、B、C和D 。

⑤ 把A和D中的每個元素與m*比較，小的放入S1，大的放入S2；

⑥S1←S1∪C;" S2←S2∪B;

⑦if k=|S1|+1 then 輸出m*

⑧else if k＜|S1|+1

⑨t(yī)hen Optimized Select （S1， k）

⑩else Optimized Select （S2， k-|S1|-1）

1） 步驟①～③：完成較好基準(zhǔn)值的選擇。

為簡單起見，假設(shè)S中元素個數(shù)是5的倍數(shù)。5個元素一組，S集合被分為[n/5]組。

每組按照從大到小排序，選擇每組的中位數(shù)，組成M集合。

使用優(yōu)化的快速選擇算法在集合M的中位數(shù)m*，即為要選擇的較好的基準(zhǔn)值。

注意：與快速選擇算法相比，選擇更好基準(zhǔn)值的過程是額外的工作，其效率必須控制在 O（n） 內(nèi)，以確保算法保持線性時間復(fù)雜度。

2） 步驟④～⑥是根據(jù)基準(zhǔn)值m*完成劃分過程。

m*將集合S劃分成4個子集，如圖2所示。其中：

B：所有元素都大于 m*。

C：所有元素都小于 m*。

A和D：所有元素需要與 m*比較，確定其應(yīng)歸入S1（小于m*） 或S2（大于m*） 。

這樣，通過基準(zhǔn)值m*將集合S劃分為了兩個子集S1和S2。

3） 步驟⑦～⑩遞歸求解選擇問題。

該過程與快速選擇算法中的遞歸過程相同，遞歸進(jìn)入其中的一個子集，求解第k小元素。

4.3 算法效率分析

接下來逐個步驟分析算法效率：

步驟①～②：每組5個數(shù)排序，可認(rèn)為效率為O（1），共有[n/5]組，總時間復(fù)雜度為O（n）。

步驟③：遞歸調(diào)用該算法找出M集合的中位數(shù)，M的數(shù)據(jù)規(guī)模為[n/5]，時間復(fù)雜度為T（n/5）。

步驟④～⑥：A和D中的元素逐個與m*進(jìn)行比較，時間復(fù)雜度為O（n）。

步驟⑦～⑩：遞歸進(jìn)入其中一個子問題。這里考慮最壞情況，即遞歸恰好進(jìn)入規(guī)模最大的子問題，則接下來需要確定子集S1和S2的規(guī)模。

設(shè)A中寬度為r，則A集合中元素個數(shù)為2r，B中為3r+2，C中為3r+2，D中為2r。因此，問題規(guī)模n=10r+5。最壞情況是A和D中的元素都放進(jìn)C或D中，子問題規(guī)模至多為7r+2，即7n/10，因此時間復(fù)雜度至多為T（7n/10）。

最終遞推方程如公式（5） 所示：

[T（n）= T（n/5） + T（7n/10）+O（n）]" " "（5）

通過遞歸樹法求解該遞推方程，最壞情況下時間復(fù)雜度為 O（n），求解過程如圖2所示。這樣，通過選擇更好的基準(zhǔn)值，確保選擇問題在最壞情況下也能在線性時間內(nèi)解決。

4.4 課后延伸思考

思考題：該算法中，將集合S分為5個元素一組。假設(shè)將分組大小調(diào)整為3個一組或者7個一組時，子問題規(guī)模將如何變化，是否仍能夠保證算法時間復(fù)雜度為O（n）？

請學(xué)生分別推導(dǎo)出兩種情況下的遞推方程，并求解相應(yīng)的時間復(fù)雜度。通過這個思考題，學(xué)生不僅能學(xué)習(xí)如何推導(dǎo)遞歸方程，還能理解分組大小變化如何直接影響算法的效率，進(jìn)而加深對算法時間復(fù)雜度分析的理解。

5 結(jié)束語

本文以選擇問題為例，深入探討了遞階式創(chuàng)新思維在算法教學(xué)中的實(shí)踐應(yīng)用。通過引導(dǎo)學(xué)生循序漸進(jìn)地優(yōu)化解決方案，不僅使學(xué)生掌握了核心算法技術(shù)，更有效培養(yǎng)了其創(chuàng)新思維和問題解決能力。遞階式教學(xué)方法采用分階段的學(xué)習(xí)模式，讓學(xué)生在逐步深入的過程中持續(xù)反思和優(yōu)化解題思路，從而顯著提升解決問題的能力。

未來研究可進(jìn)一步拓展適合遞階式教學(xué)的算法案例庫，豐富創(chuàng)新思維的培養(yǎng)路徑。同時，通過整合多樣化的教學(xué)實(shí)踐，構(gòu)建更加系統(tǒng)化的創(chuàng)新思維培養(yǎng)體系，使學(xué)生能夠靈活運(yùn)用創(chuàng)新方法應(yīng)對復(fù)雜問題。

參考文獻(xiàn)：

[1] 劉國偉，任美睿，靳雨欣，等.以培養(yǎng)計(jì)算思維能力為導(dǎo)向的算法設(shè)計(jì)與分析教學(xué)方法探索[J].計(jì)算機(jī)教育，2022（5）：189-195.

[2] 范昊，束德勤.《算法設(shè)計(jì)與分析》課程教學(xué)方法研究[J].教育教學(xué)論壇，2020（9）：246-247.

[3] 石峰，寧為，李敏，等.可視化視閾下的算法分析與設(shè)計(jì)課程翻轉(zhuǎn)教學(xué)探索[J].計(jì)算機(jī)教育，2024（2）：169-172，176.

[4] 南姣芬，楊文雅，李紅嬋，等.《算法設(shè)計(jì)與分析》教學(xué)過程中的思考[J].教育現(xiàn)代化，2019，6（35）：189-190.

[5] 孫艷蕊.圖論教學(xué)中學(xué)生創(chuàng)新思維培養(yǎng)的探索與實(shí)踐[J].高師理科學(xué)刊，2018，38（8）：82-85.

[6] 陳鵬，張璇，靳蓓蓓.創(chuàng)新思維在“計(jì)算機(jī)圖形學(xué)” 教學(xué)中的實(shí)踐[J].教育教學(xué)論壇，2020（3）：244-246.

[7] 吳寧博，楊帆，張光照，等.算法與數(shù)據(jù)結(jié)構(gòu)課程融合問題激勵的啟發(fā)式教學(xué)改革[J].計(jì)算機(jī)教育，2023（8）：76-80.

[8] 屈婉玲，劉田，張立昂，等.算法設(shè)計(jì)與分析[M].3版.北京：清華大學(xué)出版社，2023.

【通聯(lián)編輯：王 力】