最優(yōu)二叉排序樹(shù)構(gòu)建的時(shí)間復(fù)雜度分析一、引言

最優(yōu)二叉排序樹(shù)（OptimalBinarySearchTree，OBST）是數(shù)據(jù)結(jié)構(gòu)中重要的優(yōu)化問(wèn)題，旨在通過(guò)優(yōu)化樹(shù)的構(gòu)建，最小化搜索操作的平均時(shí)間復(fù)雜度。本文將詳細(xì)分析最優(yōu)二叉排序樹(shù)的構(gòu)建過(guò)程及其時(shí)間復(fù)雜度，并探討影響復(fù)雜度的關(guān)鍵因素。

二、最優(yōu)二叉排序樹(shù)的基本概念

（一）二叉排序樹(shù)定義

二叉排序樹(shù)（BST）是一種基于鍵值有序的二叉樹(shù)，滿足以下性質(zhì)：

1.若左子樹(shù)非空，則左子樹(shù)所有鍵值小于根節(jié)點(diǎn)鍵值。

2.若右子樹(shù)非空，則右子樹(shù)所有鍵值大于根節(jié)點(diǎn)鍵值。

3.左右子樹(shù)均為二叉排序樹(shù)。

（二）最優(yōu)二叉排序樹(shù)目標(biāo)

在給定一組鍵值及其訪問(wèn)概率的情況下，通過(guò)重新排列鍵值并構(gòu)建二叉排序樹(shù)，使得樹(shù)的高度最小化，從而降低搜索操作的平均時(shí)間復(fù)雜度。

三、最優(yōu)二叉排序樹(shù)的構(gòu)建方法

（一）動(dòng)態(tài)規(guī)劃方法

動(dòng)態(tài)規(guī)劃是解決最優(yōu)二叉排序樹(shù)的核心方法，通過(guò)將問(wèn)題分解為子問(wèn)題并存儲(chǔ)中間結(jié)果，避免重復(fù)計(jì)算。

1.定義子問(wèn)題

-設(shè)`e[i][j]`表示鍵值`k_i,k_{i+1},...,k_j`構(gòu)成子樹(shù)的最小搜索成本。

-設(shè)`w[i][j]`表示鍵值`k_i,k_{i+1},...,k_j`構(gòu)成子樹(shù)的權(quán)值（即所有鍵值的訪問(wèn)概率之和）。

-設(shè)`root[i][j]`表示鍵值`k_i,k_{i+1},...,k_j`構(gòu)成子樹(shù)的最優(yōu)根節(jié)點(diǎn)。

2.狀態(tài)轉(zhuǎn)移方程

-對(duì)于每個(gè)子樹(shù)`k_l`（`i≤l≤j`），計(jì)算以`k_l`為根的最小成本：

`e[i][j]=e[i][l-1]+e[l+1][j]+w[i][j]`

-選擇最優(yōu)根節(jié)點(diǎn)：

`root[i][j]=argmin_{k_l∈[i,j]}(e[i][l-1]+e[l+1][j]+w[i][j])`

3.計(jì)算順序

-從長(zhǎng)度為1的子數(shù)組開(kāi)始（即單個(gè)鍵值），逐步擴(kuò)展到整個(gè)數(shù)組。

-最終`e[1][n]`即為整個(gè)樹(shù)的最小搜索成本，`root[1][n]`為最優(yōu)根節(jié)點(diǎn)。

（二）構(gòu)建步驟

1.初始化權(quán)值矩陣`w[i][j]`：

`w[i][i-1]=0`，`w[i][j]=w[i][j-1]+p_j`（`p_j`為鍵值`k_j`的訪問(wèn)概率）。

2.初始化搜索成本矩陣`e[i][j]`：

`e[i][j]=0`（`i>j`）。

3.按子數(shù)組長(zhǎng)度遞增順序計(jì)算：

-長(zhǎng)度`l`從1到`n`：

-對(duì)于每個(gè)子數(shù)組`[i,j]`（`j-i+1=l`）：

-計(jì)算所有可能的根節(jié)點(diǎn)`k_l`，更新`e[i][j]`和`root[i][j]`。

4.遞歸構(gòu)建最優(yōu)子樹(shù)：

-根據(jù)`root[i][j]`確定左右子樹(shù)，遞歸構(gòu)建。

四、時(shí)間復(fù)雜度分析

（一）狀態(tài)轉(zhuǎn)移方程復(fù)雜度

每個(gè)狀態(tài)`e[i][j]`需要枚舉所有可能的根節(jié)點(diǎn)`k_l`，即`O(j-i+1)`次計(jì)算。

總狀態(tài)數(shù)為`O(n^2)`，每次計(jì)算復(fù)雜度`O(n)`，因此動(dòng)態(tài)規(guī)劃部分復(fù)雜度為`O(n^3)`。

（二）遞歸構(gòu)建復(fù)雜度

遞歸構(gòu)建子樹(shù)時(shí)，每次選擇根節(jié)點(diǎn)需要查詢`root[i][j]`，總遞歸次數(shù)為`O(n^2)`。

因此遞歸部分復(fù)雜度為`O(n^2)`。

（三）總復(fù)雜度

最優(yōu)二叉排序樹(shù)的構(gòu)建總時(shí)間復(fù)雜度為`O(n^3)`（動(dòng)態(tài)規(guī)劃）+`O(n^2)`（遞歸構(gòu)建）=`O(n^3)`。

五、優(yōu)化策略

（一）減少枚舉次數(shù)

（二）改進(jìn)數(shù)據(jù)結(jié)構(gòu)

使用堆或平衡樹(shù)存儲(chǔ)中間結(jié)果，將部分`O(n)`操作降為`O(logn)`。

（三）近似算法

對(duì)于大規(guī)模數(shù)據(jù)，可使用啟發(fā)式算法（如貪心策略）近似構(gòu)建最優(yōu)樹(shù)，復(fù)雜度降至`O(nlogn)`。

六、結(jié)論

最優(yōu)二叉排序樹(shù)的構(gòu)建通過(guò)動(dòng)態(tài)規(guī)劃方法實(shí)現(xiàn)，時(shí)間復(fù)雜度為`O(n^3)`。通過(guò)優(yōu)化策略可降低部分計(jì)算量，但理論復(fù)雜度仍較高。在實(shí)際應(yīng)用中，可根據(jù)數(shù)據(jù)規(guī)模選擇精確算法或近似算法。

一、引言

最優(yōu)二叉排序樹(shù)（OptimalBinarySearchTree，OBST）是數(shù)據(jù)結(jié)構(gòu)領(lǐng)域中一個(gè)重要的理論及實(shí)踐問(wèn)題。其核心目標(biāo)是在給定一組鍵值及其對(duì)應(yīng)的訪問(wèn)頻率（或概率）的情況下，通過(guò)一種特定的構(gòu)造方法，生成一棵二叉排序樹(shù)，使得在該樹(shù)上進(jìn)行搜索操作（查找、插入、刪除等）的平均時(shí)間復(fù)雜度達(dá)到最小。這與普通的二叉排序樹(shù)構(gòu)建不同，普通二叉排序樹(shù)通常按照鍵值的輸入順序構(gòu)建，其性能可能并非最優(yōu)。最優(yōu)二叉排序樹(shù)通過(guò)優(yōu)化鍵值的排列順序以及樹(shù)的結(jié)構(gòu)，能夠顯著提升在頻繁訪問(wèn)節(jié)點(diǎn)上的搜索效率。理解其構(gòu)建過(guò)程和時(shí)間復(fù)雜度，對(duì)于設(shè)計(jì)高效的搜索數(shù)據(jù)結(jié)構(gòu)具有重要的指導(dǎo)意義。

本文檔將深入探討最優(yōu)二叉排序樹(shù)的構(gòu)建方法，重點(diǎn)分析其采用動(dòng)態(tài)規(guī)劃技術(shù)的詳細(xì)步驟，并細(xì)致拆解每一步驟中的計(jì)算量，從而精確得出整個(gè)構(gòu)建過(guò)程的時(shí)間復(fù)雜度。此外，還將討論影響復(fù)雜度的關(guān)鍵因素以及可能的優(yōu)化策略。

二、最優(yōu)二叉排序樹(shù)的基本概念

（一）二叉排序樹(shù)定義

二叉排序樹(shù)（BinarySearchTree，BST）是一種基于鍵值有序存儲(chǔ)的樹(shù)形數(shù)據(jù)結(jié)構(gòu)。它滿足以下核心特性：

1.若樹(shù)的左子樹(shù)非空，則左子樹(shù)中所有節(jié)點(diǎn)的鍵值均小于其根節(jié)點(diǎn)的鍵值。

示例：若節(jié)點(diǎn)X是節(jié)點(diǎn)Y的父節(jié)點(diǎn)，且X的鍵值<Y的鍵值，則X必須是Y的左子節(jié)點(diǎn)。

2.若樹(shù)的右子樹(shù)非空，則右子樹(shù)中所有節(jié)點(diǎn)的鍵值均大于其根節(jié)點(diǎn)的鍵值。

示例：若節(jié)點(diǎn)X是節(jié)點(diǎn)Y的父節(jié)點(diǎn)，且X的鍵值>Y的鍵值，則X必須是Y的右子節(jié)點(diǎn)。

3.樹(shù)的左子樹(shù)和右子樹(shù)本身也必須是一棵二叉排序樹(shù)。

示例：以任意節(jié)點(diǎn)為根，其左子樹(shù)和右子樹(shù)都獨(dú)立遵循上述規(guī)則。

二叉排序樹(shù)支持高效的搜索、插入和刪除操作，平均情況下，這些操作的時(shí)間復(fù)雜度為O(logn)，其中n是樹(shù)中節(jié)點(diǎn)的數(shù)量。然而，其性能高度依賴于樹(shù)的高度。一棵不平衡的樹(shù)可能導(dǎo)致最壞情況下的時(shí)間復(fù)雜度為O(n)。

（二）最優(yōu)二叉排序樹(shù)目標(biāo)

最優(yōu)二叉排序樹(shù)的目標(biāo)并非簡(jiǎn)單地構(gòu)建一棵滿足BST性質(zhì)的樹(shù)，而是針對(duì)特定的鍵值集合和它們被訪問(wèn)的概率，找到一種鍵值排列方式（以及對(duì)應(yīng)的樹(shù)結(jié)構(gòu)），使得搜索操作的平均時(shí)間最短。具體定義如下：

1.鍵值集合與訪問(wèn)概率：假設(shè)有一組鍵值{k?,k?,...,k?}，每個(gè)鍵值k?有一個(gè)對(duì)應(yīng)的訪問(wèn)概率p?（通常要求p?>0，且∑p?=1）。

2.內(nèi)部節(jié)點(diǎn)與外部節(jié)點(diǎn)：在標(biāo)準(zhǔn)的OBST定義中，除了給定的鍵值（作為內(nèi)部節(jié)點(diǎn)）外，還可能引入虛擬鍵值（外部節(jié)點(diǎn)，或稱為失敗節(jié)點(diǎn)），它們代表搜索失敗的搜索路徑。通常假設(shè)每個(gè)外部節(jié)點(diǎn)有一個(gè)訪問(wèn)概率q，且所有外部節(jié)點(diǎn)的訪問(wèn)概率之和為∑q=1-∑p?。q的值可以統(tǒng)一設(shè)定（如q=1/n）或根據(jù)具體應(yīng)用場(chǎng)景分配。

3.成本函數(shù)：搜索操作的“成本”通常定義為被訪問(wèn)的節(jié)點(diǎn)數(shù)。訪問(wèn)一個(gè)內(nèi)部節(jié)點(diǎn)的成本為1，訪問(wèn)一個(gè)外部節(jié)點(diǎn)的成本為0（或可以視為常數(shù)c）。搜索成本C可以表示為所有內(nèi)部節(jié)點(diǎn)的訪問(wèn)概率與其在樹(shù)中深度（距離根節(jié)點(diǎn)的層級(jí)）的乘積之和。對(duì)于包含n個(gè)內(nèi)部節(jié)點(diǎn)和m個(gè)外部節(jié)點(diǎn)的樹(shù)，總成本C=∑?p?d?（內(nèi)部節(jié)點(diǎn)）+∑qd?（外部節(jié)點(diǎn)），其中d?是內(nèi)部節(jié)點(diǎn)k?的深度，d?是外部節(jié)點(diǎn)的深度。

4.最優(yōu)性目標(biāo)：在所有可能的二叉排序樹(shù)中，找到一棵樹(shù)，使得其總搜索成本C最小。這棵樹(shù)就是最優(yōu)二叉排序樹(shù)。

三、最優(yōu)二叉排序樹(shù)的構(gòu)建方法

（一）動(dòng)態(tài)規(guī)劃方法

動(dòng)態(tài)規(guī)劃是解決最優(yōu)二叉排序樹(shù)問(wèn)題的核心技術(shù)。其基本思想是將一個(gè)復(fù)雜問(wèn)題分解為若干個(gè)相互重疊的子問(wèn)題，先求解所有子問(wèn)題，并將結(jié)果存儲(chǔ)起來(lái)（通常使用二維數(shù)組），避免重復(fù)計(jì)算，最后通過(guò)組合子問(wèn)題的解來(lái)得到原問(wèn)題的最優(yōu)解。OBST的動(dòng)態(tài)規(guī)劃解法主要依賴于以下三個(gè)核心定義矩陣：

1.權(quán)值矩陣w[i][j]：存儲(chǔ)鍵值k?,k???,...,k?構(gòu)成的子樹(shù)中所有鍵值（包括內(nèi)部和外部節(jié)點(diǎn)）的訪問(wèn)概率之和。

計(jì)算公式：

-w[i][i-1]=0（表示空子樹(shù)的權(quán)值為0）

-w[i][j]=w[i][j-1]+p?+q（表示從子樹(shù)[i,j-1]加上當(dāng)前鍵值k?及其對(duì)應(yīng)的外部節(jié)點(diǎn)）

例如，w[1][3]=w[1][2]+p?+q。

2.搜索成本矩陣e[i][j]：存儲(chǔ)以鍵值k?,k???,...,k?構(gòu)成的最優(yōu)子樹(shù)的最小搜索成本。

3.根節(jié)點(diǎn)矩陣root[i][j]：存儲(chǔ)在最優(yōu)子樹(shù)[i,j]中作為根節(jié)點(diǎn)的鍵值k?（或k_l，其中l(wèi)是[i,j]區(qū)間內(nèi)的某個(gè)鍵值）。這個(gè)矩陣用于后續(xù)遞歸構(gòu)建樹(shù)的結(jié)構(gòu)。

動(dòng)態(tài)規(guī)劃求解OBST的過(guò)程遵循一個(gè)自底向上的策略，即先計(jì)算長(zhǎng)度最短（只包含一個(gè)鍵值）的子樹(shù)，再逐步計(jì)算更長(zhǎng)的子樹(shù)，直到計(jì)算出整個(gè)n個(gè)鍵值構(gòu)成的最優(yōu)子樹(shù)。

2.狀態(tài)轉(zhuǎn)移方程詳解

-定義子問(wèn)題：考慮鍵值集合{...k?,...,k?...}，其中1≤i≤j≤n。子問(wèn)題就是求以這j-i+1個(gè)鍵值構(gòu)成的最優(yōu)二叉排序樹(shù)的最小搜索成本e[i][j]。

-尋找最優(yōu)根節(jié)點(diǎn)：在子樹(shù)[i,j]中，我們可以選擇任何一個(gè)鍵值k_l（i≤l≤j）作為根節(jié)點(diǎn)。選擇k_l作為根節(jié)點(diǎn)意味著：

-左子樹(shù)由鍵值{k?,...,k???,k_l??}構(gòu)成，其最優(yōu)成本為e[i][l-1]。

-右子樹(shù)由鍵值{k_l??,...,k?}構(gòu)成，其最優(yōu)成本為e[l+1][j]。

-當(dāng)前選擇k_l作為根時(shí)，整棵樹(shù)的成本為左子樹(shù)成本+右子樹(shù)成本+子樹(shù)的總權(quán)值（即所有訪問(wèn)這些鍵值和對(duì)應(yīng)外部節(jié)點(diǎn)的概率之和）。

-因此，e[i][j]的值等于所有可能的根節(jié)點(diǎn)k_l對(duì)應(yīng)的成本C(l)中的最小值：

`e[i][j]=min_{l=i,...,j}{e[i][l-1]+e[l+1][j]+w[i][j]}`

-計(jì)算順序：必須按照子樹(shù)的長(zhǎng)度（即j-i+1）從小到大的順序計(jì)算。具體來(lái)說(shuō)，先計(jì)算長(zhǎng)度為1的子樹(shù)（即單個(gè)鍵值構(gòu)成的樹(shù)），然后計(jì)算長(zhǎng)度為2，3，...，n的子樹(shù)。對(duì)于長(zhǎng)度為l的子樹(shù)[i,j]，必須已經(jīng)計(jì)算出所有長(zhǎng)度小于l的子樹(shù)的成本（即所有e[i][k]和e[k+1][j]wherej-i+1<l）以及對(duì)應(yīng)的權(quán)值w[i][j]。

3.計(jì)算步驟（動(dòng)態(tài)規(guī)劃表填充分解）

-初始化：

-創(chuàng)建一個(gè)nxn的矩陣`e`，一個(gè)nxn的矩陣`root`，以及一個(gè)nxn的權(quán)值矩陣`w`。

-初始化權(quán)值矩陣`w`：

-對(duì)于所有i，設(shè)置w[i][i-1]=0。

-對(duì)于所有i和j(i<=j)，設(shè)置w[i][j]=w[i][j-1]+p[j]+q。

-初始化成本矩陣`e`：

-對(duì)于所有i，設(shè)置e[i][i-1]=0。

-填充動(dòng)態(tài)規(guī)劃表：

-按照子樹(shù)的長(zhǎng)度l從1到n進(jìn)行遍歷。

-對(duì)于每個(gè)長(zhǎng)度l，遍歷所有可能的子樹(shù)起始位置i（從1到n-l+1），計(jì)算子樹(shù)[i,i+l-1]的最優(yōu)成本e[i][i+l-1]。

-對(duì)于子樹(shù)[i,i+l-1]，遍歷所有可能的根節(jié)點(diǎn)位置l（從i到i+l-1）：

-計(jì)算選擇k_l作為根時(shí)的成本：

`cost_l=e[i][l-1]+e[l+1][i+l-1]+w[i][i+l-1]`

-如果`cost_l<e[i][i+l-1]`，則更新：

`e[i][i+l-1]=cost_l`

`root[i][i+l-1]=l`

-結(jié)果：最終，`e[1][n]`存儲(chǔ)了整個(gè)n個(gè)鍵值構(gòu)成的最優(yōu)二叉排序樹(shù)的最小搜索成本，`root[1][n]`存儲(chǔ)了該最優(yōu)樹(shù)根節(jié)點(diǎn)的鍵值索引。

（二）構(gòu)建步驟（基于動(dòng)態(tài)規(guī)劃結(jié)果）

動(dòng)態(tài)規(guī)劃表計(jì)算完成后，我們不僅得到了最優(yōu)成本，還得到了最優(yōu)樹(shù)的結(jié)構(gòu)信息（通過(guò)`root`矩陣）。以下是根據(jù)`root`矩陣遞歸構(gòu)建最優(yōu)二叉排序樹(shù)的詳細(xì)步驟：

1.初始化：準(zhǔn)備一個(gè)遞歸函數(shù)`build_OBST(i,j)`，輸入是子樹(shù)的范圍[i,j]。該函數(shù)返回一個(gè)最優(yōu)子樹(shù)的根節(jié)點(diǎn)對(duì)象（或包含鍵值、左子樹(shù)引用、右子樹(shù)引用的對(duì)象）。

2.基準(zhǔn)情況：如果`i>j`，表示子樹(shù)為空，返回`None`（空樹(shù)）。

3.遞歸構(gòu)建：

-獲取當(dāng)前子樹(shù)[i,j]的最優(yōu)根節(jié)點(diǎn)索引`r=root[i][j]`。

-創(chuàng)建根節(jié)點(diǎn)對(duì)象，鍵值為k_r。

-遞歸構(gòu)建左子樹(shù)，調(diào)用`build_OBST(i,r-1)`，將返回的子樹(shù)引用設(shè)置為當(dāng)前根節(jié)點(diǎn)的左子樹(shù)。

-遞歸構(gòu)建右子樹(shù)，調(diào)用`build_OBST(r+1,j)`，將返回的子樹(shù)引用設(shè)置為當(dāng)前根節(jié)點(diǎn)的右子樹(shù)。

-返回根節(jié)點(diǎn)對(duì)象。

4.最終樹(shù)：調(diào)用`build_OBST(1,n)`即可得到包含所有n個(gè)鍵值的最優(yōu)二叉排序樹(shù)。

四、時(shí)間復(fù)雜度分析

（一）動(dòng)態(tài)規(guī)劃部分復(fù)雜度

1.狀態(tài)數(shù)量：動(dòng)態(tài)規(guī)劃表`e`和`root`都是nxn的矩陣，共有n2個(gè)狀態(tài)需要計(jì)算。

示例：對(duì)于n個(gè)鍵值，有n2個(gè)子問(wèn)題（包括空子樹(shù)）需要求解。

2.每個(gè)狀態(tài)的計(jì)算量：

-對(duì)于狀態(tài)`e[i][j]`（`i<=j`），需要枚舉所有可能的根節(jié)點(diǎn)位置`l`，從`i`到`j`，共`j-i+1`個(gè)候選根。

-對(duì)于每個(gè)候選根`l`，計(jì)算成本需要訪問(wèn)`e[i][l-1]`和`e[l+1][j]`，這兩個(gè)值已經(jīng)預(yù)先計(jì)算好存儲(chǔ)在表中，訪問(wèn)操作是`O(1)`的。

-訪問(wèn)權(quán)值`w[i][j]`也是`O(1)`的。

-因此，計(jì)算`e[i][j]`所需的基本操作次數(shù)與子樹(shù)長(zhǎng)度`j-i+1`成正比。

3.計(jì)算順序：填充動(dòng)態(tài)規(guī)劃表時(shí)，先計(jì)算長(zhǎng)度為1的子樹(shù)（共n個(gè)），然后長(zhǎng)度為2的子樹(shù)（共n-1個(gè)），依此類推，直到長(zhǎng)度為n的子樹(shù)（共1個(gè)）。

4.總計(jì)算量（動(dòng)態(tài)規(guī)劃）：

-將所有狀態(tài)的計(jì)算量累加。對(duì)于每個(gè)長(zhǎng)度`l`（從1到n），有`n-l+1`個(gè)子樹(shù)，每個(gè)子樹(shù)的計(jì)算量與`l`成正比。

-總量≈∑(從l=1到n)[(n-l+1)l]=∑(從k=1到n)[kk]（其中k=n-l+1）

-這是一個(gè)求平方和的序列，其量級(jí)為O(n2)。

-更精確地，考慮所有狀態(tài)`e[i][j]`（`i<=j`），總共有大約n2/2個(gè)非零狀態(tài)。對(duì)于每個(gè)狀態(tài)，枚舉根節(jié)點(diǎn)的次數(shù)與子樹(shù)長(zhǎng)度`j-i+1`相關(guān)，平均來(lái)看，枚舉次數(shù)約為(n+1)/2。因此，總計(jì)算量為O(n2(n+1)/2)=O(n3)。

-結(jié)論：動(dòng)態(tài)規(guī)劃部分的計(jì)算時(shí)間復(fù)雜度為O(n3)。

（二）遞歸構(gòu)建部分復(fù)雜度

1.構(gòu)建過(guò)程：遞歸構(gòu)建樹(shù)的過(guò)程本質(zhì)上是對(duì)`root`矩陣的遍歷。每次遞歸調(diào)用`build_OBST(i,j)`時(shí)，會(huì)：

-查詢`root[i][j]`（`O(1)`）。

-遞歸調(diào)用左子樹(shù)`build_OBST(i,r-1)`（`r`是根節(jié)點(diǎn)索引）。

-遞歸調(diào)用右子樹(shù)`build_OBST(r+1,j)`。

2.節(jié)點(diǎn)遍歷次數(shù)：理論上，每個(gè)鍵值（即每個(gè)內(nèi)部節(jié)點(diǎn)）會(huì)被訪問(wèn)一次作為某個(gè)子樹(shù)的最優(yōu)根節(jié)點(diǎn)，并在遞歸過(guò)程中被訪問(wèn)一次以構(gòu)建其父節(jié)點(diǎn)。因此，遞歸過(guò)程遍歷的節(jié)點(diǎn)總數(shù)與內(nèi)部節(jié)點(diǎn)數(shù)量n成正比。

3.操作復(fù)雜度：每次遞歸調(diào)用中的主要操作是查詢`root[i][j]`和兩次遞歸調(diào)用。查詢是`O(1)`的，遞歸調(diào)用本身最終會(huì)訪問(wèn)所有節(jié)點(diǎn)。因此，遞歸構(gòu)建的整體復(fù)雜度主要取決于遞歸調(diào)用的結(jié)構(gòu)。

4.調(diào)用結(jié)構(gòu)分析：遞歸構(gòu)建的調(diào)用樹(shù)與`root`矩陣的填充過(guò)程相關(guān)。雖然每個(gè)節(jié)點(diǎn)被訪問(wèn)的次數(shù)不多，但遞歸調(diào)用的深度可能較大。對(duì)于最壞情況（如鍵值按升序或降序排列導(dǎo)致樹(shù)極度不平衡），遞歸深度可達(dá)n。然而，在平均或期望情況下，由于動(dòng)態(tài)規(guī)劃已經(jīng)預(yù)先計(jì)算了最優(yōu)根，遞歸構(gòu)建通常能維持較好的效率。

5.復(fù)雜度估算：盡管難以精確量化，但遞歸構(gòu)建的時(shí)間復(fù)雜度通常被認(rèn)為是O(n2)或O(nlogn)，取決于具體的實(shí)現(xiàn)和樹(shù)的高度分布。在OBST的動(dòng)態(tài)規(guī)劃框架下，它通常被視為一個(gè)附加步驟，其復(fù)雜度通常低于或接近于動(dòng)態(tài)規(guī)劃表的計(jì)算復(fù)雜度。為了整體分析，我們通常關(guān)注主要的動(dòng)態(tài)規(guī)劃部分。但若嚴(yán)格計(jì)算，總復(fù)雜度應(yīng)為O(n3)+O(n2)或O(n3)+O(nlogn)。

（三）總復(fù)雜度

綜合動(dòng)態(tài)規(guī)劃部分的計(jì)算和遞歸構(gòu)建部分，最優(yōu)二叉排序樹(shù)構(gòu)建的總時(shí)間復(fù)雜度主要由動(dòng)態(tài)規(guī)劃部分決定，通常被評(píng)估為O(n3)。在某些分析或優(yōu)化實(shí)現(xiàn)中，如果遞歸構(gòu)建被優(yōu)化（例如使用堆結(jié)構(gòu)），總復(fù)雜度可能表現(xiàn)為O(n3)+O(nlogn)，但O(n3)仍然是主導(dǎo)項(xiàng)。

五、優(yōu)化策略

（一）減少枚舉次數(shù)（動(dòng)態(tài)規(guī)劃優(yōu)化）

動(dòng)態(tài)規(guī)劃的核心計(jì)算在于枚舉每個(gè)子樹(shù)的所有可能根節(jié)點(diǎn)。雖然這是必要的，但可以通過(guò)以下方式微調(diào)：

1.利用對(duì)稱性：對(duì)于長(zhǎng)度為l的子樹(shù)，中間位置的根節(jié)點(diǎn)（即第?(i+j)/2?個(gè)鍵值）可能在最優(yōu)解中出現(xiàn)的概率較高。可以優(yōu)先檢查這些位置，但這通常只能提供微小的常數(shù)因子改進(jìn)。

2.記憶化搜索：對(duì)于某些特定的鍵值排列或概率分布，可能存在避免枚舉所有候選根節(jié)點(diǎn)的啟發(fā)式規(guī)則，但這具有通用性較差的問(wèn)題。

（二）改進(jìn)數(shù)據(jù)結(jié)構(gòu)

在動(dòng)態(tài)規(guī)劃計(jì)算過(guò)程中，頻繁地訪問(wèn)`e[i][j]`和`w[i][j]`。雖然使用二維數(shù)組即可，但可以探索更高效的數(shù)據(jù)結(jié)構(gòu)來(lái)存儲(chǔ)和查詢這些中間結(jié)果，尤其是在處理大規(guī)模數(shù)據(jù)時(shí)：

1.使用堆（Heap）：在計(jì)算`e[i][j]`時(shí)，需要從`e[i][l-1]`和`e[l+1][j]`中找到最小值?？梢允褂枚呀Y(jié)構(gòu)來(lái)維護(hù)候選根節(jié)點(diǎn)的成本，將查找最小值的操作從`O(l)`降低到`O(logl)`。這將動(dòng)態(tài)規(guī)劃部分的復(fù)雜度從O(n3)降低到O(n3/logn)，但仍然是多項(xiàng)式復(fù)雜度，通常記作O(n3logn)。

2.平衡樹(shù)（如AVL樹(shù)或紅黑樹(shù)）：類似于堆，也可以使用平衡樹(shù)來(lái)存儲(chǔ)中間結(jié)果，進(jìn)一步加速查找最小值的過(guò)程。

（三）近似算法

當(dāng)n的值非常大時(shí)，精確計(jì)算最優(yōu)二叉排序樹(shù)（O(n3)復(fù)雜度）可能不切實(shí)際。此時(shí)，可以采用近似算法來(lái)獲得一個(gè)足夠好的解，其計(jì)算復(fù)雜度顯著降低：

1.貪心策略：一種簡(jiǎn)單的近似方法是按照鍵值的訪問(wèn)概率`p?`的降序（或升序）對(duì)鍵值進(jìn)行排序，然后依次將它們插入到當(dāng)前最優(yōu)的BST中。這種方法的時(shí)間復(fù)雜度通常為O(nlogn)（排序）+O(nlogn)（插入），總復(fù)雜度為O(nlogn)。

2.啟發(fā)式算法：可以設(shè)計(jì)更復(fù)雜的啟發(fā)式算法，例如基于概率分布特征的加權(quán)排序等，以在O(nlogn)或O(n2)的時(shí)間復(fù)雜度內(nèi)得到性能接近最優(yōu)的樹(shù)。

這些近似算法犧牲了一定的最優(yōu)性（即構(gòu)建的樹(shù)可能不是嚴(yán)格意義上的最小搜索成本樹(shù)），但換來(lái)了顯著的速度提升，適用于對(duì)精確度要求不是極端高的場(chǎng)景。

六、結(jié)論

最優(yōu)二叉排序樹(shù)（OBST）的構(gòu)建是利用動(dòng)態(tài)規(guī)劃技術(shù)解決的一個(gè)經(jīng)典優(yōu)化問(wèn)題。其核心在于通過(guò)預(yù)先計(jì)算所有可能子樹(shù)的最優(yōu)成本和最優(yōu)根節(jié)點(diǎn)，從而避免在構(gòu)建最終樹(shù)時(shí)的冗余計(jì)算。標(biāo)準(zhǔn)的動(dòng)態(tài)規(guī)劃方法的時(shí)間復(fù)雜度為O(n3)，這使得它在處理大規(guī)模鍵值集合時(shí)可能面臨效率挑戰(zhàn)。為了應(yīng)對(duì)這一挑戰(zhàn)，可以探索多種優(yōu)化策略，例如使用堆或平衡樹(shù)來(lái)加速動(dòng)態(tài)規(guī)劃的核心計(jì)算步驟，從而將復(fù)雜度降低至O(n3logn)。對(duì)于需要極高效率但可以接受一定近似度的場(chǎng)景，可以采用基于貪心或啟發(fā)式思想的近似算法，這些算法的時(shí)間復(fù)雜度通常在O(nlogn)或O(n2)級(jí)別。理解這些方法及其復(fù)雜度，有助于根據(jù)具體的應(yīng)用需求和數(shù)據(jù)規(guī)模選擇最合適的二叉排序樹(shù)構(gòu)建策略。

一、引言

最優(yōu)二叉排序樹(shù)（OptimalBinarySearchTree，OBST）是數(shù)據(jù)結(jié)構(gòu)中重要的優(yōu)化問(wèn)題，旨在通過(guò)優(yōu)化樹(shù)的構(gòu)建，最小化搜索操作的平均時(shí)間復(fù)雜度。本文將詳細(xì)分析最優(yōu)二叉排序樹(shù)的構(gòu)建過(guò)程及其時(shí)間復(fù)雜度，并探討影響復(fù)雜度的關(guān)鍵因素。

二、最優(yōu)二叉排序樹(shù)的基本概念

（一）二叉排序樹(shù)定義

二叉排序樹(shù)（BST）是一種基于鍵值有序的二叉樹(shù)，滿足以下性質(zhì)：

1.若左子樹(shù)非空，則左子樹(shù)所有鍵值小于根節(jié)點(diǎn)鍵值。

2.若右子樹(shù)非空，則右子樹(shù)所有鍵值大于根節(jié)點(diǎn)鍵值。

3.左右子樹(shù)均為二叉排序樹(shù)。

（二）最優(yōu)二叉排序樹(shù)目標(biāo)

在給定一組鍵值及其訪問(wèn)概率的情況下，通過(guò)重新排列鍵值并構(gòu)建二叉排序樹(shù)，使得樹(shù)的高度最小化，從而降低搜索操作的平均時(shí)間復(fù)雜度。

三、最優(yōu)二叉排序樹(shù)的構(gòu)建方法

（一）動(dòng)態(tài)規(guī)劃方法

動(dòng)態(tài)規(guī)劃是解決最優(yōu)二叉排序樹(shù)的核心方法，通過(guò)將問(wèn)題分解為子問(wèn)題并存儲(chǔ)中間結(jié)果，避免重復(fù)計(jì)算。

1.定義子問(wèn)題

-設(shè)`e[i][j]`表示鍵值`k_i,k_{i+1},...,k_j`構(gòu)成子樹(shù)的最小搜索成本。

-設(shè)`w[i][j]`表示鍵值`k_i,k_{i+1},...,k_j`構(gòu)成子樹(shù)的權(quán)值（即所有鍵值的訪問(wèn)概率之和）。

-設(shè)`root[i][j]`表示鍵值`k_i,k_{i+1},...,k_j`構(gòu)成子樹(shù)的最優(yōu)根節(jié)點(diǎn)。

2.狀態(tài)轉(zhuǎn)移方程

-對(duì)于每個(gè)子樹(shù)`k_l`（`i≤l≤j`），計(jì)算以`k_l`為根的最小成本：

`e[i][j]=e[i][l-1]+e[l+1][j]+w[i][j]`

-選擇最優(yōu)根節(jié)點(diǎn)：

`root[i][j]=argmin_{k_l∈[i,j]}(e[i][l-1]+e[l+1][j]+w[i][j])`

3.計(jì)算順序

-從長(zhǎng)度為1的子數(shù)組開(kāi)始（即單個(gè)鍵值），逐步擴(kuò)展到整個(gè)數(shù)組。

-最終`e[1][n]`即為整個(gè)樹(shù)的最小搜索成本，`root[1][n]`為最優(yōu)根節(jié)點(diǎn)。

（二）構(gòu)建步驟

1.初始化權(quán)值矩陣`w[i][j]`：

`w[i][i-1]=0`，`w[i][j]=w[i][j-1]+p_j`（`p_j`為鍵值`k_j`的訪問(wèn)概率）。

2.初始化搜索成本矩陣`e[i][j]`：

`e[i][j]=0`（`i>j`）。

3.按子數(shù)組長(zhǎng)度遞增順序計(jì)算：

-長(zhǎng)度`l`從1到`n`：

-對(duì)于每個(gè)子數(shù)組`[i,j]`（`j-i+1=l`）：

-計(jì)算所有可能的根節(jié)點(diǎn)`k_l`，更新`e[i][j]`和`root[i][j]`。

4.遞歸構(gòu)建最優(yōu)子樹(shù)：

-根據(jù)`root[i][j]`確定左右子樹(shù)，遞歸構(gòu)建。

四、時(shí)間復(fù)雜度分析

（一）狀態(tài)轉(zhuǎn)移方程復(fù)雜度

每個(gè)狀態(tài)`e[i][j]`需要枚舉所有可能的根節(jié)點(diǎn)`k_l`，即`O(j-i+1)`次計(jì)算。

總狀態(tài)數(shù)為`O(n^2)`，每次計(jì)算復(fù)雜度`O(n)`，因此動(dòng)態(tài)規(guī)劃部分復(fù)雜度為`O(n^3)`。

（二）遞歸構(gòu)建復(fù)雜度

遞歸構(gòu)建子樹(shù)時(shí)，每次選擇根節(jié)點(diǎn)需要查詢`root[i][j]`，總遞歸次數(shù)為`O(n^2)`。

因此遞歸部分復(fù)雜度為`O(n^2)`。

（三）總復(fù)雜度

最優(yōu)二叉排序樹(shù)的構(gòu)建總時(shí)間復(fù)雜度為`O(n^3)`（動(dòng)態(tài)規(guī)劃）+`O(n^2)`（遞歸構(gòu)建）=`O(n^3)`。

五、優(yōu)化策略

（一）減少枚舉次數(shù)

（二）改進(jìn)數(shù)據(jù)結(jié)構(gòu)

使用堆或平衡樹(shù)存儲(chǔ)中間結(jié)果，將部分`O(n)`操作降為`O(logn)`。

（三）近似算法

對(duì)于大規(guī)模數(shù)據(jù)，可使用啟發(fā)式算法（如貪心策略）近似構(gòu)建最優(yōu)樹(shù)，復(fù)雜度降至`O(nlogn)`。

六、結(jié)論

最優(yōu)二叉排序樹(shù)的構(gòu)建通過(guò)動(dòng)態(tài)規(guī)劃方法實(shí)現(xiàn)，時(shí)間復(fù)雜度為`O(n^3)`。通過(guò)優(yōu)化策略可降低部分計(jì)算量，但理論復(fù)雜度仍較高。在實(shí)際應(yīng)用中，可根據(jù)數(shù)據(jù)規(guī)模選擇精確算法或近似算法。

一、引言

最優(yōu)二叉排序樹(shù)（OptimalBinarySearchTree，OBST）是數(shù)據(jù)結(jié)構(gòu)領(lǐng)域中一個(gè)重要的理論及實(shí)踐問(wèn)題。其核心目標(biāo)是在給定一組鍵值及其對(duì)應(yīng)的訪問(wèn)頻率（或概率）的情況下，通過(guò)一種特定的構(gòu)造方法，生成一棵二叉排序樹(shù)，使得在該樹(shù)上進(jìn)行搜索操作（查找、插入、刪除等）的平均時(shí)間復(fù)雜度達(dá)到最小。這與普通的二叉排序樹(shù)構(gòu)建不同，普通二叉排序樹(shù)通常按照鍵值的輸入順序構(gòu)建，其性能可能并非最優(yōu)。最優(yōu)二叉排序樹(shù)通過(guò)優(yōu)化鍵值的排列順序以及樹(shù)的結(jié)構(gòu)，能夠顯著提升在頻繁訪問(wèn)節(jié)點(diǎn)上的搜索效率。理解其構(gòu)建過(guò)程和時(shí)間復(fù)雜度，對(duì)于設(shè)計(jì)高效的搜索數(shù)據(jù)結(jié)構(gòu)具有重要的指導(dǎo)意義。

本文檔將深入探討最優(yōu)二叉排序樹(shù)的構(gòu)建方法，重點(diǎn)分析其采用動(dòng)態(tài)規(guī)劃技術(shù)的詳細(xì)步驟，并細(xì)致拆解每一步驟中的計(jì)算量，從而精確得出整個(gè)構(gòu)建過(guò)程的時(shí)間復(fù)雜度。此外，還將討論影響復(fù)雜度的關(guān)鍵因素以及可能的優(yōu)化策略。

二、最優(yōu)二叉排序樹(shù)的基本概念

（一）二叉排序樹(shù)定義

二叉排序樹(shù)（BinarySearchTree，BST）是一種基于鍵值有序存儲(chǔ)的樹(shù)形數(shù)據(jù)結(jié)構(gòu)。它滿足以下核心特性：

1.若樹(shù)的左子樹(shù)非空，則左子樹(shù)中所有節(jié)點(diǎn)的鍵值均小于其根節(jié)點(diǎn)的鍵值。

示例：若節(jié)點(diǎn)X是節(jié)點(diǎn)Y的父節(jié)點(diǎn)，且X的鍵值<Y的鍵值，則X必須是Y的左子節(jié)點(diǎn)。

2.若樹(shù)的右子樹(shù)非空，則右子樹(shù)中所有節(jié)點(diǎn)的鍵值均大于其根節(jié)點(diǎn)的鍵值。

示例：若節(jié)點(diǎn)X是節(jié)點(diǎn)Y的父節(jié)點(diǎn)，且X的鍵值>Y的鍵值，則X必須是Y的右子節(jié)點(diǎn)。

3.樹(shù)的左子樹(shù)和右子樹(shù)本身也必須是一棵二叉排序樹(shù)。

示例：以任意節(jié)點(diǎn)為根，其左子樹(shù)和右子樹(shù)都獨(dú)立遵循上述規(guī)則。

二叉排序樹(shù)支持高效的搜索、插入和刪除操作，平均情況下，這些操作的時(shí)間復(fù)雜度為O(logn)，其中n是樹(shù)中節(jié)點(diǎn)的數(shù)量。然而，其性能高度依賴于樹(shù)的高度。一棵不平衡的樹(shù)可能導(dǎo)致最壞情況下的時(shí)間復(fù)雜度為O(n)。

（二）最優(yōu)二叉排序樹(shù)目標(biāo)

最優(yōu)二叉排序樹(shù)的目標(biāo)并非簡(jiǎn)單地構(gòu)建一棵滿足BST性質(zhì)的樹(shù)，而是針對(duì)特定的鍵值集合和它們被訪問(wèn)的概率，找到一種鍵值排列方式（以及對(duì)應(yīng)的樹(shù)結(jié)構(gòu)），使得搜索操作的平均時(shí)間最短。具體定義如下：

1.鍵值集合與訪問(wèn)概率：假設(shè)有一組鍵值{k?,k?,...,k?}，每個(gè)鍵值k?有一個(gè)對(duì)應(yīng)的訪問(wèn)概率p?（通常要求p?>0，且∑p?=1）。

2.內(nèi)部節(jié)點(diǎn)與外部節(jié)點(diǎn)：在標(biāo)準(zhǔn)的OBST定義中，除了給定的鍵值（作為內(nèi)部節(jié)點(diǎn)）外，還可能引入虛擬鍵值（外部節(jié)點(diǎn)，或稱為失敗節(jié)點(diǎn)），它們代表搜索失敗的搜索路徑。通常假設(shè)每個(gè)外部節(jié)點(diǎn)有一個(gè)訪問(wèn)概率q，且所有外部節(jié)點(diǎn)的訪問(wèn)概率之和為∑q=1-∑p?。q的值可以統(tǒng)一設(shè)定（如q=1/n）或根據(jù)具體應(yīng)用場(chǎng)景分配。

3.成本函數(shù)：搜索操作的“成本”通常定義為被訪問(wèn)的節(jié)點(diǎn)數(shù)。訪問(wèn)一個(gè)內(nèi)部節(jié)點(diǎn)的成本為1，訪問(wèn)一個(gè)外部節(jié)點(diǎn)的成本為0（或可以視為常數(shù)c）。搜索成本C可以表示為所有內(nèi)部節(jié)點(diǎn)的訪問(wèn)概率與其在樹(shù)中深度（距離根節(jié)點(diǎn)的層級(jí)）的乘積之和。對(duì)于包含n個(gè)內(nèi)部節(jié)點(diǎn)和m個(gè)外部節(jié)點(diǎn)的樹(shù)，總成本C=∑?p?d?（內(nèi)部節(jié)點(diǎn)）+∑qd?（外部節(jié)點(diǎn)），其中d?是內(nèi)部節(jié)點(diǎn)k?的深度，d?是外部節(jié)點(diǎn)的深度。

4.最優(yōu)性目標(biāo)：在所有可能的二叉排序樹(shù)中，找到一棵樹(shù)，使得其總搜索成本C最小。這棵樹(shù)就是最優(yōu)二叉排序樹(shù)。

三、最優(yōu)二叉排序樹(shù)的構(gòu)建方法

（一）動(dòng)態(tài)規(guī)劃方法

動(dòng)態(tài)規(guī)劃是解決最優(yōu)二叉排序樹(shù)問(wèn)題的核心技術(shù)。其基本思想是將一個(gè)復(fù)雜問(wèn)題分解為若干個(gè)相互重疊的子問(wèn)題，先求解所有子問(wèn)題，并將結(jié)果存儲(chǔ)起來(lái)（通常使用二維數(shù)組），避免重復(fù)計(jì)算，最后通過(guò)組合子問(wèn)題的解來(lái)得到原問(wèn)題的最優(yōu)解。OBST的動(dòng)態(tài)規(guī)劃解法主要依賴于以下三個(gè)核心定義矩陣：

1.權(quán)值矩陣w[i][j]：存儲(chǔ)鍵值k?,k???,...,k?構(gòu)成的子樹(shù)中所有鍵值（包括內(nèi)部和外部節(jié)點(diǎn)）的訪問(wèn)概率之和。

計(jì)算公式：

-w[i][i-1]=0（表示空子樹(shù)的權(quán)值為0）

-w[i][j]=w[i][j-1]+p?+q（表示從子樹(shù)[i,j-1]加上當(dāng)前鍵值k?及其對(duì)應(yīng)的外部節(jié)點(diǎn)）

例如，w[1][3]=w[1][2]+p?+q。

2.搜索成本矩陣e[i][j]：存儲(chǔ)以鍵值k?,k???,...,k?構(gòu)成的最優(yōu)子樹(shù)的最小搜索成本。

3.根節(jié)點(diǎn)矩陣root[i][j]：存儲(chǔ)在最優(yōu)子樹(shù)[i,j]中作為根節(jié)點(diǎn)的鍵值k?（或k_l，其中l(wèi)是[i,j]區(qū)間內(nèi)的某個(gè)鍵值）。這個(gè)矩陣用于后續(xù)遞歸構(gòu)建樹(shù)的結(jié)構(gòu)。

動(dòng)態(tài)規(guī)劃求解OBST的過(guò)程遵循一個(gè)自底向上的策略，即先計(jì)算長(zhǎng)度最短（只包含一個(gè)鍵值）的子樹(shù)，再逐步計(jì)算更長(zhǎng)的子樹(shù)，直到計(jì)算出整個(gè)n個(gè)鍵值構(gòu)成的最優(yōu)子樹(shù)。

2.狀態(tài)轉(zhuǎn)移方程詳解

-定義子問(wèn)題：考慮鍵值集合{...k?,...,k?...}，其中1≤i≤j≤n。子問(wèn)題就是求以這j-i+1個(gè)鍵值構(gòu)成的最優(yōu)二叉排序樹(shù)的最小搜索成本e[i][j]。

-尋找最優(yōu)根節(jié)點(diǎn)：在子樹(shù)[i,j]中，我們可以選擇任何一個(gè)鍵值k_l（i≤l≤j）作為根節(jié)點(diǎn)。選擇k_l作為根節(jié)點(diǎn)意味著：

-左子樹(shù)由鍵值{k?,...,k???,k_l??}構(gòu)成，其最優(yōu)成本為e[i][l-1]。

-右子樹(shù)由鍵值{k_l??,...,k?}構(gòu)成，其最優(yōu)成本為e[l+1][j]。

-當(dāng)前選擇k_l作為根時(shí)，整棵樹(shù)的成本為左子樹(shù)成本+右子樹(shù)成本+子樹(shù)的總權(quán)值（即所有訪問(wèn)這些鍵值和對(duì)應(yīng)外部節(jié)點(diǎn)的概率之和）。

-因此，e[i][j]的值等于所有可能的根節(jié)點(diǎn)k_l對(duì)應(yīng)的成本C(l)中的最小值：

`e[i][j]=min_{l=i,...,j}{e[i][l-1]+e[l+1][j]+w[i][j]}`

-計(jì)算順序：必須按照子樹(shù)的長(zhǎng)度（即j-i+1）從小到大的順序計(jì)算。具體來(lái)說(shuō)，先計(jì)算長(zhǎng)度為1的子樹(shù)（即單個(gè)鍵值構(gòu)成的樹(shù)），然后計(jì)算長(zhǎng)度為2，3，...，n的子樹(shù)。對(duì)于長(zhǎng)度為l的子樹(shù)[i,j]，必須已經(jīng)計(jì)算出所有長(zhǎng)度小于l的子樹(shù)的成本（即所有e[i][k]和e[k+1][j]wherej-i+1<l）以及對(duì)應(yīng)的權(quán)值w[i][j]。

3.計(jì)算步驟（動(dòng)態(tài)規(guī)劃表填充分解）

-初始化：

-創(chuàng)建一個(gè)nxn的矩陣`e`，一個(gè)nxn的矩陣`root`，以及一個(gè)nxn的權(quán)值矩陣`w`。

-初始化權(quán)值矩陣`w`：

-對(duì)于所有i，設(shè)置w[i][i-1]=0。

-對(duì)于所有i和j(i<=j)，設(shè)置w[i][j]=w[i][j-1]+p[j]+q。

-初始化成本矩陣`e`：

-對(duì)于所有i，設(shè)置e[i][i-1]=0。

-填充動(dòng)態(tài)規(guī)劃表：

-按照子樹(shù)的長(zhǎng)度l從1到n進(jìn)行遍歷。

-對(duì)于每個(gè)長(zhǎng)度l，遍歷所有可能的子樹(shù)起始位置i（從1到n-l+1），計(jì)算子樹(shù)[i,i+l-1]的最優(yōu)成本e[i][i+l-1]。

-對(duì)于子樹(shù)[i,i+l-1]，遍歷所有可能的根節(jié)點(diǎn)位置l（從i到i+l-1）：

-計(jì)算選擇k_l作為根時(shí)的成本：

`cost_l=e[i][l-1]+e[l+1][i+l-1]+w[i][i+l-1]`

-如果`cost_l<e[i][i+l-1]`，則更新：

`e[i][i+l-1]=cost_l`

`root[i][i+l-1]=l`

-結(jié)果：最終，`e[1][n]`存儲(chǔ)了整個(gè)n個(gè)鍵值構(gòu)成的最優(yōu)二叉排序樹(shù)的最小搜索成本，`root[1][n]`存儲(chǔ)了該最優(yōu)樹(shù)根節(jié)點(diǎn)的鍵值索引。

（二）構(gòu)建步驟（基于動(dòng)態(tài)規(guī)劃結(jié)果）

動(dòng)態(tài)規(guī)劃表計(jì)算完成后，我們不僅得到了最優(yōu)成本，還得到了最優(yōu)樹(shù)的結(jié)構(gòu)信息（通過(guò)`root`矩陣）。以下是根據(jù)`root`矩陣遞歸構(gòu)建最優(yōu)二叉排序樹(shù)的詳細(xì)步驟：

1.初始化：準(zhǔn)備一個(gè)遞歸函數(shù)`build_OBST(i,j)`，輸入是子樹(shù)的范圍[i,j]。該函數(shù)返回一個(gè)最優(yōu)子樹(shù)的根節(jié)點(diǎn)對(duì)象（或包含鍵值、左子樹(shù)引用、右子樹(shù)引用的對(duì)象）。

2.基準(zhǔn)情況：如果`i>j`，表示子樹(shù)為空，返回`None`（空樹(shù)）。

3.遞歸構(gòu)建：

-獲取當(dāng)前子樹(shù)[i,j]的最優(yōu)根節(jié)點(diǎn)索引`r=root[i][j]`。

-創(chuàng)建根節(jié)點(diǎn)對(duì)象，鍵值為k_r。

-遞歸構(gòu)建左子樹(shù)，調(diào)用`build_OBST(i,r-1)`，將返回的子樹(shù)引用設(shè)置為當(dāng)前根節(jié)點(diǎn)的左子樹(shù)。

-遞歸構(gòu)建右子樹(shù)，調(diào)用`build_OBST(r+1,j)`，將返回的子樹(shù)引用設(shè)置為當(dāng)前根節(jié)點(diǎn)的右子樹(shù)。

-返回根節(jié)點(diǎn)對(duì)象。

4.最終樹(shù)：調(diào)用`build_OBST(1,n)`即可得到包含所有n個(gè)鍵值的最優(yōu)二叉排序樹(shù)。

四、時(shí)間復(fù)雜度分析

（一）動(dòng)態(tài)規(guī)劃部分復(fù)雜度

1.狀態(tài)數(shù)量：動(dòng)態(tài)規(guī)劃表`e`和`root`都是nxn的矩陣，共有n2個(gè)狀態(tài)需要計(jì)算。

示例：對(duì)于n個(gè)鍵值，有n2個(gè)子問(wèn)題（包括空子樹(shù)）需要求解。

2.每個(gè)狀態(tài)的計(jì)算量：

-對(duì)于狀態(tài)`e[i][j]`（`i<=j`），需要枚舉所有可能的根節(jié)點(diǎn)位置`l`，從`i`到`j`，共`j-i+1`個(gè)候選根。

-對(duì)于每個(gè)候選根`l`，計(jì)算成本需要訪問(wèn)`e[i][l-1]`和`e[l+1][j]`，這兩個(gè)值已經(jīng)預(yù)先計(jì)算好存儲(chǔ)在表中，訪問(wèn)操作是`O(1)`的。

-訪問(wèn)權(quán)值`w[i][j]`也是`O(1)`的。

-因此，計(jì)算`e[i][j]`所需的基本操作次數(shù)與子樹(shù)長(zhǎng)度`j-i+1`成正比。

3.計(jì)算順序：填充動(dòng)態(tài)規(guī)劃表時(shí)，先計(jì)算長(zhǎng)度為1的子樹(shù)（共n個(gè)），然后長(zhǎng)度為2的子樹(shù)（共n-1個(gè)），依此類推，直到長(zhǎng)度為n的子樹(shù)（共1個(gè)）。

4.總計(jì)算量（動(dòng)態(tài)規(guī)劃）：

-將所有狀態(tài)的計(jì)算量累加。對(duì)于每個(gè)長(zhǎng)度`l`（從1到n），有`n-l+1`個(gè)子樹(shù)，每個(gè)子樹(shù)的計(jì)算量與`l`成正比。

-總量≈∑(從l=1到n)[(n-l+1)l]=∑(從k=1到n)[kk]（其中k=n-l+1）

-這是一個(gè)求平方和的序列，其量級(jí)為O(n2)。

-更精確地，考慮所有狀態(tài)`e[i][j]`（`i<=j`），總共有大約n2/2個(gè)非零狀態(tài)。對(duì)于每個(gè)狀態(tài)，枚舉根節(jié)點(diǎn)的次數(shù)與子樹(shù)長(zhǎng)度`j-i+1`相關(guān)，平均來(lái)看，枚舉次數(shù)約為(n+1)/2。因此，總計(jì)算量為O(n2(n+1)/2)=O(n3)。

-結(jié)論：動(dòng)態(tài)規(guī)劃部分的計(jì)算時(shí)間復(fù)雜度為O(n3)。

（二）遞歸構(gòu)建部分復(fù)雜度

1.構(gòu)建過(guò)程：遞歸構(gòu)建樹(shù)的過(guò)程本質(zhì)上是對(duì)`root`矩陣的遍歷。每次遞歸調(diào)用`build_OBST(i,j)`時(shí)，會(huì)：

-查詢`root[i][j]`（`O(1)`）。

-遞歸調(diào)用左子樹(shù)`build_OBST(i,r-1)`（`r`是根節(jié)點(diǎn)索引）。

-遞歸調(diào)用右子樹(shù)`build_OBST(r+1,j)`。

2.節(jié)點(diǎn)遍歷次數(shù)：理論上，每個(gè)鍵值（即每個(gè)內(nèi)部節(jié)點(diǎn)）會(huì)被訪問(wèn)一次作為某個(gè)子樹(shù)的最優(yōu)根節(jié)點(diǎn)，并在遞歸過(guò)程中被訪問(wèn)一次以構(gòu)建其父節(jié)點(diǎn)。因此，遞歸過(guò)程遍歷的節(jié)點(diǎn)總數(shù)與內(nèi)部節(jié)點(diǎn)數(shù)量n成正比。

3.操作復(fù)雜度：每次遞歸調(diào)用中的主要操作是查詢`root[i][j]`和兩次遞歸調(diào)用。查詢是`O(1)`的，遞歸調(diào)用本身最終會(huì)訪問(wèn)所有節(jié)點(diǎn)。因此，遞歸構(gòu)建的整體復(fù)雜度主要取決于遞歸調(diào)用的結(jié)構(gòu)。

4.調(diào)用結(jié)構(gòu)分析：遞歸構(gòu)建的調(diào)用樹(shù)與`root`矩陣的填充過(guò)程相關(guān)。雖然每個(gè)節(jié)點(diǎn)被訪問(wèn)的次數(shù)不多，但遞歸調(diào)用的深度可能較大。對(duì)于最壞情況（如鍵值按升序或降序排列導(dǎo)致樹(shù)極度不平衡），遞歸深度可達(dá)n。然