111 年 國立臺灣大學生醫電子與資訊學研究所丙組《計算機概論（B）》

本大題共考 20 個名詞解釋，每個名詞佔 2 分，總計 40 分。要求定義、內容、目的、應用，並舉例，若可能則以數學式定義，若是縮寫則需寫出全名。以下依序條列詳解。

(1) Hamming error correction code:

• 定義: Hamming 碼是一種能夠偵測並修正單一錯誤的線性分組碼，也能偵測部分多重錯誤。
• 內容: 在原始資料位元中加入額外的檢查位元（parity bits），這些檢查位元的位置和值是根據特定規則計算出來的，以便在接收端能定位並修正錯誤。
• 目的: 提高資料傳輸或儲存的可靠性，確保資料在傳輸過程中發生的錯誤可以被自動偵測及修正。
• 應用: 廣泛應用於記憶體（如 DRAM）、硬碟、衛星通訊、光碟等需要高可靠性資料儲存與傳輸的場合。
• 舉例: 若原始資料為 1011，加入檢查位元後可能變成 1101011 (其中粗體為檢查位元)。若傳輸過程中某一位元錯誤，接收端可透過檢查碼計算出錯誤位置並修正。

(2) Wi-Fi: Wireless Fidelity:

• 定義: Wi-Fi（Wireless Fidelity）是一種無線網路技術標準，允許裝置在不使用實體線路的情況下，透過無線電波連接到網路。
• 內容: 基於 IEEE 802.11 系列標準，定義了無線區域網路（WLAN）的技術規範，包括頻段、傳輸速率、安全協定等。
• 目的: 提供便利、靈活的無線網路連接，擺脫實體線路的限制，讓裝置能隨時隨地接入網際網路或區域網路。
• 應用: 筆記型電腦、智慧型手機、平板電腦、智慧家電等各種裝置的無線上網，無線基地台（AP）的部署。
• 舉例: 在咖啡廳、機場、家中，使用手機或筆電連接無線網路，即是使用 Wi-Fi 技術。

(3) context switching in multitasking:

• 定義: 在多工（multitasking）作業系統中，上下文切換（context switching）是指 CPU 從執行一個處理程序（process）或執行緒（thread）暫時轉移到執行另一個處理程序或執行緒的過程。
• 內容: 在切換過程中，作業系統需要儲存當前執行程序的所有狀態資訊（如 CPU 暫存器值、程式計數器、記憶體管理資訊等），並載入下一個要執行的程序狀態。
• 目的: 讓使用者感覺多個程式同時在運行，提高 CPU 的利用率，實現多工處理。
• 應用: 所有支援多工的作業系統，如 Windows, macOS, Linux, Android, iOS 等。
• 舉例: 當你正在打字，同時有音樂在播放，作業系統在 CPU 上快速地在打字程式和音樂播放程式之間切換，這就是上下文切換。

(4) Dijkstra's algorithm for shortest path:

• 定義: Dijkstra 演算法是一種用於尋找圖中單源點到所有其他頂點之間最短路徑的圖演算法。
• 內容: 該演算法從起始點開始，逐步擴展已知最短路徑的頂點集合，每次選擇距離起始點最近的未訪問頂點，並更新其鄰居頂點的距離。
• 目的: 在帶權重的圖中，找到從一個指定節點到圖中所有其他節點的最短路徑。
• 應用: 網路路由（如 OSPF 協定）、地圖導航系統、交通規劃、物流配送路線規劃等。
• 舉例: 在地圖應用程式中，輸入起點和終點，程式計算出最短或最快路徑，就可能使用了 Dijkstra 演算法。

(5) CNN: Convolutional Neural Network:

• 定義: CNN（Convolutional Neural Network）是一種特別適用於處理具有網格結構資料（如圖像）的深度學習模型。
• 內容: 其核心是卷積層（convolutional layers），這些層使用卷積核（kernels）在輸入數據上滑動，提取局部特徵。還包含池化層（pooling layers）和全連接層（fully connected layers）。
• 目的: 自動學習資料中的空間層次結構和特徵，特別擅長圖像識別、物件偵測、語音辨識等任務。
• 應用: 圖像辨識（人臉辨識、手寫數字辨識）、醫學影像分析、自動駕駛、自然語言處理中的某些任務。
• 舉例: Google Photos 的人臉辨識功能，或手機相機的場景辨識功能，都可能使用了 CNN。

(6) ReLU: Rectified Linear Unit:

• 定義: ReLU（Rectified Linear Unit）是一種神經網路中常用的激活函數（activation function）。
• 內容: 其數學定義為 $f(x) = \max(0, x)$。對於輸入的負值，輸出為 0；對於輸入的正值，輸出為其本身。
• 目的: 引入非線性，使得神經網路能夠學習更複雜的模式。相較於 sigmoid 或 tanh，ReLU 計算簡單、收斂速度快，且能緩解梯度消失問題。
• 應用: 廣泛應用於深度學習模型，特別是卷積神經網路（CNN）和多層感知機（MLP）。
• 舉例: 當神經元接收到的加權輸入總和是 -2，ReLU 函數的輸出是 0；若總和是 3，輸出則是 3。

(7) average pooling:

• 定義: 平均池化（average pooling）是一種在卷積神經網路中用於降低特徵圖空間尺寸（解析度）的操作。
• 內容: 將輸入特徵圖劃分為若干個不重疊的區域（或可重疊，取決於具體實現），並計算每個區域內所有像素值的平均值作為輸出的值。
• 目的: 減少參數數量，降低計算複雜度，防止過度擬合，並在一定程度上保持特徵的平移不變性。
• 應用: CNN 中，通常在卷積層之後、激活函數之前或之後使用，以逐步縮小特徵圖的尺寸。
• 舉例: 一個 2x2 的平均池化操作，將一個 4x4 的區域的 16 個像素值求平均，得到一個 2x2 的輸出區域。

(8) batch normalization:

• 定義: 批次標準化（batch normalization）是一種用於加速深度神經網路訓練並提高其穩定性的技術。
• 內容: 在訓練過程中，對每一層的輸入進行標準化處理，使其具有零均值和單位方差。但為了保留模型表達能力，會引入可學習的縮放（gamma）和偏移（beta）參數。
• 目的: 緩解內部協變量偏移（Internal Covariate Shift）問題，允許使用更高的學習率，加速收斂，並起到一定的正則化作用。
• 應用: 廣泛應用於各種深度學習模型，特別是當網路層數較深時。
• 舉例: 在一個神經網路層的輸出經過激活函數之前，批次標準化會計算該層在當前訓練批次中的均值和方差，然後對每個樣本的輸出進行標準化，再乘以 gamma 並加上 beta。

(9) RISC: Reduced Instruction Set Computer:

• 定義: RISC（Reduced Instruction Set Computer）是一種電腦架構設計理念，強調使用數量較少、簡單且執行速度快的指令集。
• 內容: 指令集設計精簡，大部分指令都可以在一個時鐘週期內完成。複雜的運算通常需要多個簡單指令組合而成。強調使用暫存器進行資料處理。
• 目的: 提高處理器效率，降低設計複雜度，減少功耗，並加快指令執行速度。
• 應用: ARM 架構處理器（廣泛用於智慧型手機、平板電腦）、MIPS、PowerPC 等。
• 舉例: ARM 處理器是 RISC 架構的典型代表，其指令集相對精簡，效率高。

(10) finite state machine:

• 定義: 有限狀態機（finite state machine, FSM）是一種數學模型，用於描述一個系統，該系統可以在有限個狀態之間轉換，並且在任何給定時間只能處於其中一個狀態。
• 內容: 由一組狀態（states）、一個初始狀態（initial state）、一個輸入字母表（input alphabet）、一個轉換函數（transition function）和一個輸出函數（output function，可選）組成。
• 目的: 模擬和描述具有離散狀態和事件驅動行為的系統。
• 應用: 編譯器（詞法分析）、數位電路設計、協定分析、遊戲邏輯、簡單的 AI 行為等。
• 舉例: 自動販賣機可以看作一個有限狀態機。它的狀態包括「等待投幣」、「等待選擇商品」、「找零」等，投入硬幣或選擇商品是觸發狀態轉換的事件。

(11) packet in local area network:

• 定義: 在區域網路（LAN）中，封包（packet）是網路傳輸的資料單位。
• 內容: 資料被分割成較小的單元，每個單元都包含原始資料片段以及控制資訊（如來源與目的 MAC 位址、IP 位址、埠號、檢查碼等），這些控制資訊構成了封包的標頭（header）和尾部（trailer）。
• 目的: 使得網路能夠更有效地處理和路由資料，支援多個裝置同時通訊，並提供錯誤偵測機制。
• 應用: 所有基於 TCP/IP 或其他分封交換網路的通訊，如瀏覽網頁、收發電子郵件、線上遊戲等。
• 舉例: 當你瀏覽網頁時，網頁的資料會被分割成許多 TCP/IP 封包，透過網路傳輸到你的電腦。

(12) page in for virtual memory:

• 定義: 在虛擬記憶體系統中，「頁面調入」（page in）是指將儲存在輔助儲存（如硬碟）上的資料頁面載入到主記憶體（RAM）的過程。

本題考 P2P 網路的全名，以及 P2P 網路與 Client-Server 網路的差異、優缺點。

P2P 網路的全名:
P2P 是 Peer-to-Peer 的縮寫。

P2P 網路與 Client-Server 網路的比較:

特性	P2P (Peer-to-Peer) 網路	Client-Server 網路
架構	節點（peer）既是資源提供者，也是資源消費者，沒有專門的伺服器。每個節點都可以直接與其他節點通訊。	有專門的伺服器（server）提供服務，而客戶端（client）向伺服器請求服務。客戶端與客戶端之間通常不直接通訊。
資源分配	分散式，資源分散在各個節點上。	集中式，資源集中在伺服器上。
通訊方式	節點之間直接通訊（點對點）。	客戶端透過伺服器間接通訊，或直接向伺服器請求資源。
管理	分散式管理，難以集中控制。	集中式管理，由伺服器統一管理。
擴展性	難以擴展，隨著節點增多，管理和查找資源的難度增加。	易於擴展，可透過增加伺服器或升級伺服器來處理更多客戶端請求。
可靠性	較高，單一節點故障不影響整個網路運行（除非是關鍵資源提供者）。

本題考以 Bitcoin 為例，說明區塊鏈（blockchain）的工作原理。

區塊鏈（Blockchain）的工作原理（以 Bitcoin 為例）:

區塊鏈是一種分散式、不可篡改的數位帳本技術，它記錄了所有交易的歷史。Bitcoin 的區塊鏈記錄了所有 Bitcoin 交易。其工作原理可以概括為以下幾個關鍵步驟：

1. 交易發生與廣播:

   • 當一位使用者（A）想要向另一位使用者（B）發送 Bitcoin 時，A 會創建一個交易訊息，其中包含 A 的數位簽章（證明交易的有效性）、A 的公開金鑰、B 的公開金鑰（或 Bitcoin 地址）、交易的金額，以及 A 的錢包（使用私鑰）簽署的授權。
   • 這個交易訊息會被廣播到 Bitcoin 網路中的其他節點（參與者）。

2. 節點驗證交易:

   • 網路中的節點（特別是礦工節點）會接收到這個交易廣播。
   • 節點會驗證交易的有效性，主要包括：
     • 檢查 A 的數位簽章是否正確，確認 A 確實擁有這些 Bitcoin。
     • 檢查 A 是否有足夠的 Bitcoin 來完成這次交易，即檢查 A 的交易歷史記錄（在區塊鏈上）。

3. 打包交易成區塊:

   • 被驗證為有效的交易會進入一個「待處理交易池」（mempool）。
   • 礦工（Miners）從這個池中選擇一批交易，將它們打包在一起，形成一個「區塊」（Block）。
   • 每個區塊還包含：
     • 前一個區塊的哈希值（Hash），這就是將區塊鏈連接起來的關鍵。
     • 一個隨機數（Nonce），用於工作量證明（Proof-of-Work, PoW）。
     • 時間戳。

4. 工作量證明（Proof-of-Work, PoW）:

   • 礦工們需要解決一個計算難題，這個難題要求他們找到一個特定的 Nonce 值，使得將區塊的標頭（header）與這個 Nonce 一起進行哈希計算後，得到的結果（哈希值）必須小於或等於

本題考傳值（pass by value）與傳址（pass by reference）的差異、優缺點。這兩種是函式呼叫時傳遞參數的兩種主要方式。

1. 傳值 (Pass by Value)

• 定義: 當參數是傳值時，函式呼叫時會將實際參數的值複製一份，然後將這個副本傳遞給函式。函式內部對參數副本所做的任何修改，都不會影響到實際參數。
• 差異: 函式接收的是參數的「值」的副本。
• 優點:
  • 安全性: 函式內部無法意外修改到呼叫端的原始變數，保護了原始資料。
  • 獨立性: 函式操作獨立於呼叫端，不會產生副作用。
• 缺點:
  • 效率較低: 對於大型資料結構（如陣列、結構體），複製整個資料會消耗較多的時間和記憶體。
  • 無法修改原始資料: 如果函式需要修改呼叫端的原始變數，傳值方式無法實現。

2. 傳址 (Pass by Reference)

• 定義: 當參數是傳址時，函式呼叫時不會複製參數的值，而是將實際參數的記憶體位址（或稱為參考）傳遞給函式。函式內部對參數的修改，實際上是直接修改了原始變數的值。
• 差異: 函式接收的是參數的「記憶體位址」或「參考」。
• 優點:
  • 效率高: 傳遞的是位址，對於大型資料結構，傳遞位址的開銷遠小於複製整個資料。
  • 可修改原始資料: 函式可以透過傳遞的位址直接修改呼叫端的原始變數，實現參數的「回傳」功能。
• 缺點:
  • 安全性較低: 函式內部可能會意外修改到呼叫端的原始變數，產生難以預料的副作用。
  • 副作用: 函式對參數的修改會直接影響呼叫端，有時難以追蹤。

總結比較:

| 特性 | 傳值 (Pass by Value) | 傳址 (Pass by Reference)

本題考軟體系統生命週期的五個主要階段。軟體生命週期（Software Development Life Cycle, SDLC）是指一個軟體從概念形成、開發、測試、部署到維護的整個過程。雖然不同模型（如 Waterfall, Agile, Spiral）有不同的劃分方式，但核心階段通常包含以下五個：

軟體系統生命週期的五個階段:

1. 需求分析 (Requirements Analysis)

   • 說明: 這是軟體開發的第一步，也是最關鍵的階段之一。在這個階段，開發團隊與客戶（或使用者）緊密合作，收集、定義、分析和記錄軟體的全部需求。這包括功能性需求（軟體應該做什麼）和非功能性需求（如效能、安全性、可用性、可靠性等）。
   • 目的: 確保開發團隊對專案的目標有清晰、準確的理解，並為後續的設計和開發奠定堅實的基礎。錯誤的需求定義是導致專案失敗的主要原因之一。
   • 產出物: 通常是需求規格說明書（Software Requirements Specification, SRS），其中詳細列出所有功能和非功能性需求。

2. 系統設計 (System Design)

   • 說明: 在需求確定後，進入系統設計階段。此階段的目標是定義軟體的整體架構和詳細設計。它包括兩個層次：
     • 高階設計 (High-level Design, HLD): 定義系統的模組劃分、模組間的關係、資料流、系統架構等。
     • 低階設計 (Low-level Design, LLD): 對每個模組進行詳細設計，包括資料結構、演算法、介面定義、錯誤處理機制等。
   • 目的: 將抽象的需求轉化為具體的藍圖，指導後續的程式碼編寫。良好的設計能夠提高軟體的模組化、可維護性、可擴展性和效率。
   • 產出物: 設計規格說明書（Design Specification），可能包含架構圖、資料庫設計、介面規格等。

3. 實作與測試 (Implementation and Testing)

   • 說明: 這是將設計藍圖轉化為實際可執行程式碼的階段。開發人員根據設計規格編寫程式碼，並進行單元測試（Unit Testing）。
   • 測試: 測試是這個階段的核心活動。它涉及多個層次：
     • 單元測試 (Unit Testing): 測試獨立的程式碼模組或函數。

本題考 RSA 公鑰加密系統及其公鑰與私鑰的概念。

RSA (Rivest-Shamir-Adleman) 公鑰加密系統

RSA 是一種廣泛使用的非對稱加密演算法，也是最早由 Ron Rivest, Adi Shamir, 和 Leonard Adleman 在 1977 年提出的公鑰密碼系統之一。它基於一個數學難題：兩個大質數的乘積很容易計算，但要從這個乘積反推出這兩個質數則非常困難（即大數分解的難題）。

RSA 系統包含以下幾個關鍵部分：

1. 金鑰對生成 (Key Generation):

   • 選擇兩個極大的隨機質數 $p$ 和 $q$。
   • 計算模數 $n = p \times q$。
   • 計算 $\phi(n) = (p-1)(q-1)$（歐拉函數）。
   • 選擇一個整數 $e$，使得 $1 < e < \phi(n)$ 且 $e$ 與 $\phi(n)$ 互質（即 $\text{gcd}(e, \phi(n)) = 1$）。$e$ 通常選擇為 65537，因為它是一個質數且計算效率高。
   • 計算 $d$，使得 $d \times e \equiv 1 \pmod{\phi(n)}$。$d$ 是 $e$ 在模 $\phi(n)$ 下的模反元素。
   • 公鑰 (Public Key) 由 $(e, n)$ 組成，可以公開給任何人。
   • 私鑰 (Private Key) 由 $(d, n)$ 組成，必須由金鑰持有者嚴格保密。

2. 加密 (Encryption):

   • 假設傳送者 Alice 想給接收者 Bob 發送訊息 $M$（$M$ 必須是一個數字，且 $0 \le M < n$）。
   • Alice 使用 Bob 的公鑰 $(e, n)$ 來加密訊息：
     $C = M^e \pmod{n}$
   • Alice 將密文 $C$ 發送給 Bob。

3. 解密 (Decryption):

   • Bob 收到密文 $C$ 後，使用自己的私鑰 $(d, n)$ 來解密：

本題考費氏數列（Fibonacci sequence）的遞迴定義方程式，以及列出其前十項數字。

費氏數列的遞迴定義方程式:

費氏數列是一個數列，其中每個數字是前兩個數字的總和。它的定義如下：

• 基礎情況 (Base Cases):

  • $F_0 = 0$
  • $F_1 = 1$

• 遞迴關係 (Recursive Relation):

  • 對於 $n > 1$，費氏數列的第 $n$ 項 $F_n$ 定義為：
    $F_n = F_{n-1} + F_{n-2}$

前十項費氏數列:

根據上述定義，我們可以計算出費氏數列的前十項：

核心觀念

本題考查三種算術表達式：

• Prefix（前序式）：運算子在兩個運算元之前。
• Infix（中序式）：運算子位於兩個運算元之間，通常以括號明確表示運算順序。
• Postfix（後序式）：運算子在兩個運算元之後。

題目中的運算子 +、-、*、/ 皆為二元運算子，每個運算子需要接收左、右兩個運算元或子表達式。

原式：

$$-*-/ab*cd+efg$$

依前序式切割為：

$$- \quad * \quad - \quad / \quad a \quad b \quad * \quad c \quad d \quad + \quad e \quad f \quad g$$

解題方法

由前序式的結構可知，最前面的 - 是整個表達式的根運算子。

依序建立子表達式：

1. /ab：

$$\frac{a}{b}$$

2. *cd：

$$c*d$$

3. -/ab*cd：

$$\left(\frac{a}{b}-(c*d)\right)$$

4. +ef：

$$(e+f)$$

5. *-/ab*cd+ef：

$$\left(\left(\frac{a}{b}-(c*d)\right)*(e+f)\right)$$

6. 最後與 g 進行減法：

$$\left(\left(\frac{a}{b}-(c*d)\right)*(e+f)\right)-g$$

因此，加上完整括號的中序式為：

本題考使用者資料報協定（UDP）與傳輸控制協定（TCP）的比較，包含差異、優點與缺點。兩者都是網路層（IP）之上的傳輸層協定，但提供不同的服務。

1. 傳輸控制協定 (TCP - Transmission Control Protocol)

• 類型: 連接導向（Connection-Oriented）的傳輸層協定。
• 連接建立: 在資料傳輸前，TCP 需要透過「三向交握」（Three-way Handshake）建立一個邏輯連線。
• 可靠性:
  • 確認應答 (Acknowledgement, ACK): 接收端收到資料後必須回傳 ACK，若發送端未收到 ACK，則會重傳資料。
  • 序列號 (Sequence Numbers): 資料被分割成段（Segments），每個段都有序列號，確保資料按正確順序接收。
  • 重傳機制 (Retransmission): 若資料丟失或損壞，TCP 會重傳。
  • 流量控制 (Flow Control): 透過接收端緩衝區大小，防止發送端傳送過多資料導致接收端溢出。
  • 擁塞控制 (Congestion Control): 監測網路擁塞情況，調整傳輸速率，避免網路癱瘓。
• 優點:
  • 可靠性極高: 確保資料的準確、完整、有序到達。
  • 錯誤檢測與恢復: 能有效處理資料丟失、重複、損壞和亂序問題。
  • 適合關鍵應用: 適用於對資料準確性要求極高的應用，如網頁瀏覽 (HTTP/HTTPS)、檔案傳輸 (FTP)、電子郵件 (SMTP)。
• 缺點:
  • 開銷較大: 需要建立連接、傳送 ACK、管理序列號等，增加了額外的網路和處理開銷。
  • 傳輸速度較慢: 由於可靠性機制，TCP 的傳輸速度通常比 UDP 慢。
  • 延遲較高: 連接建立和重傳機制會引入延遲。
  • 頭部較大: TCP 報頭（Header）通常為 20 位元組，包含更多控制資訊。

2. 使用者資料報協定 (UDP - User Datagram Protocol)

• 類型: 無連接（Connectionless）的傳輸層協定。
• 連接建立: 無需建立連接，直接發送資料報（Datagram）。
• 可靠性:
  • 盡力而為 (Best-Effort): UDP 只負責將資料報發送出去，不保證資料是否能到達、是否按順序到達，也不保證資料的完整性。
  • 無確認應答、無重傳: 發送端發送後就不再關心，接收端不回傳 ACK，也沒有重傳機制。
  • 無序列號: 資料報是獨立的單元，順序不保證。
  • 無流量控制、無擁塞控制: UDP 不會主動調節傳輸速率。
• 優點:
  • 開銷小: 無需建立連接、管理序列號等，開銷非常低。
  • 傳輸速度快: 由於沒有可靠性機制，資料傳輸速度快。
  • 延遲低: 傳輸過程中延遲非常小。
  • 頭部小: UDP 報頭僅 8 位元組，非常簡潔。

核心觀念

本題考查二補數（two's complement）在定點二進位數中的表示法。

二補數的基本規則為：

1. 先寫出正數的二進位表示。
2. 對所有位元逐位取反。
3. 最低有效位加 $1$。

小數部分必須以二進位小數表示：

$$0.625=0.5+0.125=2^{-1}+2^{-3}=0.101_2$$

因此：

$$21.625=10101.101_2$$

題目未指定位元數與小數位數，以下採用「整數部分 8 位元、小數部分 3 位元」的定點格式表示。

---

解題方法

1. 寫出正數 $+21.625$

整數部分：

$$21=10101_2$$

補足為 8 位元：

$$21=00010101_2$$

小數部分：

$$0.625=0.101_2$$

所以：

$$+21.625=00010101.101_2$$

2. 逐位取反

$$00010101.101 \longrightarrow 11101010.010$$

小數點不變，整數與小數部分的每一個位元均取反。

3. 加上 $1$

本題考合併排序法（Mergesort）的詳細說明，以及對一組數字進行合併排序的步驟。

合併排序法 (Mergesort)

合併排序法是一種基於「分治法」（Divide and Conquer）的排序演算法。它的基本思想是：

1. 分割 (Divide): 將待排序的序列遞迴地分割成兩個大小大致相同的子序列，直到每個子序列只包含一個元素（一個單獨的元素本身就是一個已排序的序列）。
2. 合併 (Conquer): 將分割得到的子序列兩兩合併，並在合併的過程中進行排序，直到最後合併成一個完整的、已排序的序列。

演算法詳細步驟:

1. 分割階段:

   • 如果序列的長度為 0 或 1，則它已經是有序的，直接返回。
   • 否則，找到序列的中點，將序列分割成左半部分和右半部分。
   • 遞迴地對左半部分和右半部分分別執行合併排序。

2. 合併階段:

   • 假設我們有兩個已排序的子序列，分別為左子序列 (L) 和右子序列 (R)。
   • 創建一個新的空序列（或使用額外的空間）來存放合併後的結果。
   • 使用兩個指標，一個指向 L 的開頭 (i)，一個指向 R 的開頭 (j)。
   • 比較 L[i] 和 R[j] 的值：
     • 如果 L[i] 小於或等於 R[j]，則將 L[i] 複製到結果序列中，並將 i 向後移動一位。
     • 否則，將 R[j] 複製到結果序列中，並將 j 向後移動一位。
   • 重複上述比較和複製過程，直到其中一個子序列的所有元素都被複製到結果序列中。
   • 將另一個子序列中剩餘的元素（如果有的話）直接複製到結果序列的末尾。
   • 將結果序列複製回原序列的對應位置。

時間複雜度:
合併排序法的時間複雜度在所有情況下（最好、最壞、平均）都是 $O(n \log n)$，其中 $n$ 是序列的長度。這是因為分割階段需要 $\log n$ 層遞迴，而每一層的合併階段需要 $O(n)$ 的時間來處理所有元素。

空間複雜度:
合併排序法需要額外的空間來存放合併過程中產生的臨時序列，其空間複雜度為 $O(n)$。

---

對序列 6, 5, 3, 1, 8, 7, 2, 4 進行合併排序:

原始序列：[6, 5, 3, 1, 8, 7, 2, 4] (長度 n=8)

第一層分割:

• 分割成左半 [6, 5, 3, 1] 和右半 [8, 7, 2, 4]。
• 遞迴處理左半 [6, 5, 3, 1]。
• 遞迴處理右半 [8, 7, 2, 4]。

第二層分割 (處理左半 [6, 5, 3, 1]):

• 分割成 [6, 5] 和 [3, 1]。
• 遞迴處理 [6, 5]。
• 遞迴處理 [3, 1]。

第二層分割 (處理右半 [8, 7, 2, 4]):

• 分割成 [8, 7] 和 [2, 4]。
• 遞迴處理 [8, 7]。
• 遞迴處理 [2, 4]。

第三層分割 (處理 [6, 5]):

• 分割成 [6] 和 [5]。
• [6] 和 [5] 都是單個元素，已排序。
• 合併 [6] 和 [5]:
  • 比較 6 和 5。5 較小。結果：[5]。i 指向 6。
  • 複製剩餘的 6。結果：[5, 6]。
  • 左半部分 [6, 5] 排序後為 [5, 6]。

第三層分割 (處理 [3, 1]):

• 分割成 [3] 和 [1]。
• [3] 和 [1] 都是單個元素，已排序。
• 合併 [3] 和 [1]:
  • 比較 3 和 1。1 較小。結果：[1]。i 指向 3。
  • 複製剩餘的 3。結果：[1, 3]。
  • 左半部分 [3, 1] 排序後為 [1, 3]。

第三層分割 (處理 [8, 7]):

• 分割成 [8] 和 [7]。
• [8] 和 [7] 都是單個元素，已排序。
• 合併 [8] 和 [7]:
  • 比較 8 和 7。7 較小。結果：[7]。i 指向 8。
  • 複製剩餘的 8。結果：[7, 8]。
  • 右半部分 [8, 7] 排序後為 [7, 8]。

第三層分割 (處理 [2, 4]):

• 分割成 [2] 和 [4]。
• [2] 和 [4] 都是單個元素，已排序。
• 合併 [2] 和 [4]:
  • 比較 2 和 4。2 較小。結果：[2]。i 指向 4。
  • 複製剩餘的 4。結果：[2, 4]。
  • 右半部分 [2, 4] 排序後為 [2, 4]。

---

回到第一層合併:

本題要求證明對於任意整數 $n$，表達式 $\frac{n}{3} + \frac{n^2}{2} + \frac{n^3}{6}$ 的結果一定是一個整數，並舉例驗證。

證明:

我們可以將這個表達式合併，然後嘗試證明其分子是 6 的倍數。
令 $E(n) = \frac{n}{3} + \frac{n^2}{2} + \frac{n^3}{6}$。
為了合併分數，我們找到共同分母 6：
$E(n) = \frac{2n}{6} + \frac{3n^2}{6} + \frac{n^3}{6}$
$E(n) = \frac{n^3 + 3n^2 + 2n}{6}$
現在我們需要證明分子 $n^3 + 3n^2 + 2n$ 是 6 的倍數。
我們可以對分子進行因式分解：
$n^3 + 3n^2 + 2n = n(n^2 + 3n + 2)$
$n^2 + 3n + 2$ 可以因式分解為 $(n+1)(n+2)$。
所以，分子可以寫成：
$n(n+1)(n+2)$

現在，我們需要證明 $n(n+1)(n+2)$ 是 6 的倍數。
$n(n+1)(n+2)$ 是三個連續整數的乘積。

性質:

1. 連續整數的乘積必含有偶數: 在任何兩個連續的整數中，必定有一個是偶數（即是 2 的倍數）。在三個連續整數 $n, n+1, n+2$ 中，至少有一個是偶數。因此，$n(n+1)(n+2)$ 必定是 2 的倍數。
2. 連續整數的乘積必含有 3 的倍數: 在任何三個連續的整數中，必定有一個是 3 的倍數。
   • 考慮 $n \pmod 3$:
     • 若 $n \equiv 0 \pmod 3$，則 $n$ 是 3 的倍數。
     • 若 $n \equiv 1 \pmod 3$，則 $n+2 \equiv 1+2 \equiv 3 \equiv 0 \pmod 3$，$n+2$ 是 3 的倍數。
     • 若 $n \equiv 2 \pmod 3$，則 $n+1 \equiv 2+1 \equiv 3 \equiv 0 \pmod 3$，$n+1$ 是 3 的倍數。
   • 所以，在 $n, n+1, n+2$ 中，必定有一個是 3 的倍數。因此，$n(n+1)(n+2)$ 必定是 3 的倍數。

由於 $n(n+1)(n+2)$ 同時是 2 的倍數和 3 的倍數，而 2 和 3 是互質的，所以 $n(n+1)(n+2)$ 必定是 $2 \times 3 = 6$ 的倍數。

因此，$\frac{n(n+1)(n+2)}{6}$ 必定是一個整數。
這就證明了原表達式 $\frac{n}{3} + \frac{n^2}{2} + \frac{n^3}{6}$ 對於任意整數 $n$ 都是一個整數。

舉例驗證:

我們來驗證 $n=1, 2, 3, ..., 10$ 的情況。
我們計算 $E(n) = \frac{n(n+1)(n+2)}{6}$。

• n=1: $E(1) = \frac{1(1+1)(1+2)}{6} = \frac{1 \times 2 \times 3}{6} = \frac{6}{6} = 1$ (整數)
• n=2: $E(2) = \frac{2(2+1)(2+2)}{6} = \frac{2 \times 3 \times 4}{6} = \frac{24}{6} = 4$ (整數)
• n=3: $E(3) = \frac{3(3+1)(3+2)}{6} = \frac{3 \times 4 \times 5}{6} = \frac{60}{6} = 10$ (整數)
• n=4: $E(4) = \frac{4(4+1)(4+2)}{6} = \frac{4 \times 5 \times 6}{6} = 4 \times 5 = 20$ (整數)