알고리즘 Chapter 3

这边在这里 他说树的左半边的节点 一定小于等于 这边的节点一定小于等于 上面这一个 那你说这个要怎么看 这个他以字母来看 书上这个例子他以字母来看 所以你看一下 第一个字母是不是都以R来的小于等于 右侧这边都是大于等于 所以他这边写小于等于跟大于等于

這是它的一個很重要的 也算一個比例而已 它只是1分左右 那你看這一棵樹有嗎? 如果說以這邊來看 這個的確小一點 右邊這邊呢

都大於等於他 對不對 所以看起來有 那我們在看的時候 不是只有看根節點 我們要看所有的節點 所有節點的一個組合 所以我們再看細部的部分 比如說 講說這一半部 這一半部如果以他為標準的話 這個是不是小於等於他 這邊三個是不是大於等於他 那同樣的假設我們以這邊來看

以它為標準的話 這個是不是小一點點它 這個是不是大一點點它 如果都是的話 它就符合頒順序的一個基本的條件 我們先看看這邊有沒有問題 這是二元搜尋書 除了說它要是二元數之外 它必須是二元數之外 但額外的一個條件就是它的桌子數 就每一個前點的桌子數跟桌子數的一個狀況

可以嗎? 那左右指數的話也不一定說你有左右指數就一定有左右指數 所以他又多了最前面這個一開始的小條件 他說每個Node必須含有一個T 對 不好意思這個T是指這個 還有一個字 還有一個字 那額外提的說左右指數就每一個Node不一定都有左邊

右邊不一定 但是它只會有左邊 或者是兩邊都有 不可能會再有第三個 不可能再有第三個根子 來 我們先看這邊有問題 然後書上的話對各位還不錯 就是簡單的再多一點點樹狀結構的一些小概念 但是是配合這個Vanace Street 它定義了幾個名詞 一個是深度 這個是深度的

或者是層,就是Lagos 這兩個是一樣的,一樣的東西 那就是它的H的一個數量 從root到它H的一個數量 所以如果我們以前這個圖來看的話 把這個消掉 如果以左邊這個圖來看的話 它的root的話,它的深入是0

就书上的一个说明 那再来是1 因为root到这一个 到这个节点它有一个age 那这边是2 那root到这个节点 或是到这个节点都有两个age 从上面这样下来 都有两个age 那这个是stime

所以他說他的那個深度 是Numple of Edge的數量 那如果以右側這邊來看就是012 那你會發現因為在同一個橫向他們的深度都一樣 所以他的深度這個名詞又稱為Label 你可以說他們是同一層

同學先這樣對應看看有沒有問題 那這樹上的話它是說 root的部分 樹根的部分 level是0 低影層 深度是0 因為它沒有AB 它根上面沒有AB下來 所以是B這樣子

那它有一個名詞叫Balance 就是它的左右指數的深度 就是不能差1超過1 就是可以兩邊一樣 就是比如說像 這邊 這個可以 左右一樣都可以

左右一樣 或者是說他如果不小心這邊再多一個左分枝 也可以 這個也是balance的狀況 就是左右 左右差異 左右差異 但是這個的話他就不行了 這個就不行了 如果依照他更 應該是說他還是balance 但是他沒有達到balance的一個條件 因為他的左指數這邊是深度是1 但是右指數最深到3 那他們的差異就超過3-1就2 就超過1 就是說他還是辦一個設置區 但是如果說要達到balance的條件的話 就沒有辦法 左邊就沒有 右邊可以 右邊可以 右邊可以

來這邊可以嗎 這是書上一開始 對於Bine-A Search Tree這邊 給同學一些些的一些文字上的一些提醒 那這邊有一個就是 如果你要去Search這個Bine-A Tree的話 你要去搜尋它的話 它給你一個演算法 這個演算法跟動態溝化目前還沒有關係 它是一個設施的一個動作 那

嗯,來一下,我可以好像前一個3.2節 那邊我好像也問過一些樹狀結構的一些走訪的一些方法 那這邊的話就是如果現在是,這個是它本身是一個Bine-A-Tree 那你要做一個簡單的搜尋動作的話,他說你可以這麼做

各位可以看一下它跑回圈 那一開始它把key 就是看你能不能找key就是那個節點 那個節點的字 看是不是你要的 如果是那就除了 就找到了 那如果不是的話 它現在是找你的

左侧 找你的左侧 不然就是找你的右侧 那符合Lel's以赴这个条件的话 找你的左侧 不然就找你的右侧 所以他目前的一个做法就是 如果说我们要找 假设我们要找轮值在 这边好了 这边 那一开始从这里来 那他会先看是不是

是不是 那接下來到底找左找右呢 那就看他的一個 接下來這兩個 因為這是多選一嘛 那就看符合else 還是符合else 那他說如果是小於的話 你要找的 你要找的這個T 你要找這個子 如果小於 小於 目前的一個節點的話 那就往左邊找

那如果大於目前的節點就往右邊走 那所以如果說目前這邊來說話 我們現在是以字母來看 來用這個單字的字首這個字母 來看大於小於 所以現在我要找這個 這個tom tom 那他比這個r 這個t比這個r還要來的大 所以等一下我們應該是走 右側

就是走這個 Fails這個條件 走右側 然後接下來到這邊的時候 那T比U小 所以會走左側 然後接下來到這裡的時候 它就是變成找到了 它就變成在這個演算法裡面 會到第一個部分 就找到了 就這邊 最後就到這邊

那這個是根據你目前二元素素狀結構 它所寫出來的一個演算法 有左分支 所以它就一個P箭頭 P指向的一個左邊 這個就你們的那個 Nicker List的一個結構 所以指向左側或者是指向右側

來,同學先看這個問題 這邊還不是動態規劃 這邊只是簡單的給你一個 如果你要去搜尋你要的內容的時候 那你可以怎麼去規劃這個演算法 來,同學到這邊可以嗎? OK,這邊都還比較簡單 一些開場的一些東西 那重點來了,31頁

那我們在這個 現在這個是3.4節 不是,這是3.5節 3.5節這個 這裡它最重要的一個目的在做什麼呢? 它要去看最佳的一個搜尋時間 應該說平均的一個搜尋時間 從平均搜尋時間裡面要去找最佳的 最佳的平均搜尋時間 所以這一頁從這樣,1.31頁開始 那如果你是輸的話 應該是從

123頁下方會開始的 那就開始在進入它的核心的一個重點 那這邊才開始做動態規劃的動作 那首先我們一個一個來看 他說我們先看什麼叫做搜尋時間 搜尋時間 它定義所謂的搜尋時間 剛才我們這邊就是一個簡單的搜尋動作

對不對?我剛剛有示範一個簡單的搜尋動作 比如說我要找Tom 那我們先從Root開始找 然後發現要往右邊找 然後又跟他比 然後發現要往左邊找 然後終於找到 這個找的動作他現在稱為搜尋時間 那搜尋時間就是你要比較的次數 你那個每次在比較的時候這個次數 所以是這一個 如果照剛才來說就是這一個 這組也不用的一個比較的一個次數

好,ok 那這個比較次數他說還蠻簡單的 如果就我們目前的一個觀察的話 就是深度 目前這個節點的深度加1就可以了 就是他的比較次數 就是他的比較次數 所以他舉例 舉例這一個 那這個深度目前在 我們看一下

他现在是用 他目前这个例子好像是用左侧这个图 看一下 深度他是说2 那2的话他举例的例子是左侧这个图 左侧这个图 因为这个图刚差太快了 嗯

1 2 3 所以他現在是以左側這個圖來決定 那目前他的深度在第二層 第二個level 所以他的比較次數就是 從上面開始 他會先跟他比 比一次 然後接下來往右側走 因為他比較大嘛 所以會往右側走 所以再跟他比一次 再一次 再往右側走 再比一次 這樣第三次 所以一次兩次三次 所以他都這個三次 就是你目前的生物的值 加一到就是比較次數三次 就是比較次數三次

同學看這邊有沒有問題 所以他說比較次數就是我們的search time 以目前來說就是search time 那比較次數的話還蠻簡單的 就是目前的深度+1 就是我們的比較次數 OK嗎 OK 那這邊的話我看一下 這應該有路應的一個例

維合範例3.7,我沒有拍照例上

P這個變數是說 如果以這個例子 意思就是

我要搜尋P2的一個基率 跟我要搜尋P3的一個基率 就是說P1這個點 讓你被搜尋的那個點的 幾率大概是70% 那P2這個點 讓你被搜尋的那個點的幾率是 20% 同比P3是0.1% 10% 所以有個幾率

因為我們在剛才講一個30頁的第二個部分要看平均的收取時間 那平均的話我們以前在講平均的時候 在路達路平均的時候平均就有機率之進來 所以這邊一樣有機率之進來 就是第一個點要當search key 的一個機率是多少 第二個點要當search key 的多少 那第三個點要當search key 的機率是多少

那我們剛才有講說比較次數跟深度有關 跟深度有關 所以現在以目前翻譯三點級 它有三個key 那三個key要組成finance search tree的話 有不同方式 第一 二、三、四 有這個不同方式 那這三個key的話 我們有這個編號key K1、K2、K3

那我以編號來看 K3是最大 K2是第二大 K1最小 K1最小 大概這樣子 所以我們先觀察這五個翻譯設計器的一個図體樣式 各位先看看有沒有符合我的規則 我的規則就是哪個點上面到有T 那這邊有問題 這是第一個規則 那第二個規則就是 各個節點的左側都要比

接點小 小一點接點 他的右側都要大一點 所以我們這邊看 這邊有沒有 以他來說 K3 這邊都比較小 然後K2 這個也比較小 所以這邊也是 如果K3在這裡的話 那K1 K2在左邊 都比較大 那如果以這個K1來看的話 這個K2比較大 所以沒有問題 那這邊也是

這邊也是 所以如果現在是Section T的話 K1 K2 K3的順序剛好就跟123的順序是一樣的 1是最小 3是最大 所以我目前上面這五個數量結構 都符合Binance Search Tree的一個基礎條件 我先看這邊有沒有問題

那現在就是由這五個tree 這五個樹狀結構來看看 怎樣的一個組合 它的搜尋時間會最小 搜尋時間會最小 所以這個跟我們前一個 我們沒有提到的那個連鎖矩身相乘 也是同樣的意思 它就是要看怎麼乘那個四數會最少 那這邊一樣我們要把那個tree建出來 那建出來的這個tree要讓它搜尋的時間是最少的 平均搜尋時間是最少的

那是有問題 那平均搜尋時間怎麼看呢 我們剛才已經知道搜尋時間了 搜尋時間跟每個Key的搜尋時間跟深度有關 跟深度有關 深度加1 所以第一個的話 那他的搜尋時間可能會多少 我們先看K1 我們都起來在這邊

這是第0層 這是第1層 2層 整個這樣過去嘛 都一樣 所以 K1 現在在第2層 那 K1 的一個 貝商搜尋Q 的一個機率高達0.7 所以是2 欸 抱歉 是2+1是3 搜尋次數是乘數加上1 所以是3 然後乘上0.7

然後這個K2搜尋key的機率是0.2 K2現在是在第一層 第一層+1/2 所以比較四處12乘上0.2 然後再加上這個K3 K3就在root

所以他比較是11 等下0點 所以第一個算出來 這是第一個 第一個算出來現在是 我把它放一下 我把它放一下 2.6 平均收尋

所以次數是2.64 那如果是第二個的話 我寫在上面 那K1現在是在第一層 所以它的次數現在是第一層加1就是2 甚至0.7 K2現在是在第2層 這是第二層 然後次數是三次 2加1是3 所以上0.2

然後這個還是在第0層 所以是EB 所以這算出來是不是 2.1 所以第二個 如果第一個是這樣做的話 平均收取時間是26 如果是這樣做的話 平均收取時間是1 所以不同的一個結構方式 它的平均收取時間不一樣

我先1.5 那剩下這個我就不寫出來 直接寫答案答案 這個算出來是1.8 然後這個是1.5 這個是1.4 所以如果現在翻13.7給你三個key 然後他們分別被當作搜尋key的幾率 幾率分別是0.70.2 0.1的話 如果是這樣的組合的話 那平均收取時間要最少 那組合方式就是這一個

因為他平均收取次數只有一點 平均收取時間啊 就是他的次數就1.4 就只有1.4 那像這個的話 如果你是這邊的花圍膠206 我們會快差兩倍 快差兩倍 我們可以在意理解一下

所以機率值,還有它的一個key的數量,還有它的結構的一個狀況 都會影響到它整個平均收取的一個時間的一個在比較的一個種次數會有差別 第二個,因爲這個是在第一名,那這個是,這個二就是乘數加一

這個也是啊,這是乘數加1 因為這個現在是在第二層 乘數加1,然後這在第一層,乘數加1 這個都是,這個是乘數 這三是,它在第二層,所以是2加1 然後這個第三,它在第零層,0加1

同學先看這題案例3.7 先給各位這樣的一個概念

所以我們先從,我們等於是先從範例來看 從範例來看,然後看回來他的一個狀況 那,我們對照一下 平均搜尋時間,就我們剛剛現在範例3點7在做 那他說會有一個P的一個變數,PM 所以它是一個跑DL,是一個機率值 就是這個KM,KeyM,當作搜尋Key的一個機率 就是我要搜尋它,我要搜尋的那個Key就是它 那機率有多少 那C,C這個變數就是比較次數 就上面這個比較次數 所以呢,平均搜尋時間就在上面這個 就是你的比較次數跟機率值相準 然後再把它做一個sumation的一個動作 就架走

可以嗎

先看等號右側,等下等號左側這個AIZ再做說明 先看等號右側這一塊 先看看這裡有沒有 我們剛做的是在這裡 我們剛做的動作是這一個 搭配這兩個 就有轉圈的綠色的部分 那個等一下AIZ 等一下再看 綠色的這個部分跟PMC 就是剛一個是機率子,一個是比較低 剛換第三個已經在算了

然後我們現在要慢慢的把那個矩陣把它帶進去 因為我們現在這個主題是動態規劃 動態規劃裡面每一個主題都有一個對應的矩陣要算 都有一個對應的矩陣要算 所以我們要先把綠色這個部分先調情去 綠色部分給我剛剛可以把它寫 這個可以嗎 那現在我們要開始對應到我們矩陣 那我這邊用的矩陣叫他的代號就叫A A這個矩陣AIZ它也是一個二維矩陣

那AiJ如果配應對應剛才我們這個加總的一個動作的話 那他就是AiJ就是M 今天這就是M,就是M從I到J 那其中AiI就是PI 就是沒有C這個變數 如果是AiI的話 C這個變數是沒有的,就只有PI 等一下我們要來做對應

我一定要用剛才的例子

次數跟機率相乘 然後次數機率相乘 次數去加起來 然後加起來對不對 連加動作 然後加起來 所以是等號右側 那現在我要對應到等號左側 如果說我們等一下要搭配一個舉證 叫做A舉證 那它是一個二維舉證 那以目前這邊來說的話 我們現在算的這個值 其實它是對應在哪裡 是A

以目前这样来看,我们现在算的这个值 就是我们有三个P,编号123 所以123 对不对? 所以I就是1,J就是3 所以我们现在算的这个内容 它是A这个矩阵里面A13的内容 对不对,我们现在算的这个内容,这个是

這個也是 這邊全部都是A13的內容 但是最適合的是這一個 我們最終A13的內容要除的是最小的這一個 因為我們A13的組合可能有很多種 但是最適合的是這一種 因為它算出來最小 只最小

所以現在我們現在念三個P 所以DIK等於是KI到KIJ KI1到KI3 1到3 所以我們現在算的這些值全部都在A矩正裡面 A3的一個位置 來 同學先看到這邊有沒有問題

那如果以白話文來解釋 目前A13是什麼 就是如果我們現在有三個key 編號123 那就是從第一個key到第三個key 它的最佳 最佳的一個平均搜尋時間 記憶的內容就會放在這裡 再做一次白話文的解釋 我們現在這個題目是三個key 這三個key要組成的一個fine search 它的一個最佳的一個搜尋時間 算出來之後 會放在這個地方 因為一個key到第三個key

所以總共三個 編號1號到編號3號 就是這個意思 有沒有問題 那如果沒問題的話 要請同學思考一下呢 為什麼AII就是PI 如果上面那個了解的話 那現在AII為什麼是PI

你不想再去吧

首先上面的要會回答

就是說我們剛才這邊已經講 如果以目前這個範例叫做A13 就是因為它有三個key 編號1號到編號3號 這三個key所構成的最佳的 就是二元搜尋數的最佳搜尋時間 算出來這個只要放在矩陣A13的位置

那我們現在反問同學那AII什麼意思呢 那有時候我們就是帶個數字進去嘛 比如說AII,那I如果是E的話 那就是AEE嘛 AEE是什麼意思 就是只有一個key 編號叫做E號 就是KE嘛 只有一個key編號叫E號 KE嘛 對不對 那 所以整個數狀結構就只有他

我去理解嗎 如果我現在要算這一個A11 整個樹狀結構只有它 這樣才叫A111號點到1號點 它就自己 那它的機率目前是0.7 照原本提供 目前是0.7 那它在哪一個level 在地底的level 那比較次數是什麼 比加1就是0.4 所以等於是0.7乘上1嘛

次數一次,然後接受一點心 所以那乘以1跟有成沒成是一樣的 所以等於是它的 直接是它的機率值 對不對 所以現在如果是 i 是 1 的話 這個直接是 p 1 對不對 那如果是 a 2 2 i 如果是 2

A22什麼意思?就是你的樹脹結構就只有一個二號點 二號點到二號點 那就這樣一點 那二號點的機率是多少? 以目前的題目來說是0.2 所以如果這個是2的話 這應該是P1 這個就P2 等下如果是3的話就這樣

所以AI的意思就是說 整個圖形結構上就他 就他自己 那I看是1還是2還是3 那就1號點自己 2號點自己 或是3號點自己 那自己的話 因為他就是在路德上面 那level是你次數 所以一層上 次數一層上機率值 那就是他的機率值 所以這個一就沒有 次數又沒有

所以解釋往地 這是A矩陣 先看看這邊的問題 我們再看一下

然後範例3.8 我可以看一下 同樣的例子 範例3.8現在是這樣 要我們算A2

算你3.8,他要你算A23是多少 A23是什么意思?同样的例子 就是2号点跟3号点的组合 那如果我们先画图的话,那可能就只有两种 就是K3、K2、K3 就是这两种,对不对?这两种

那這兩種的話 最小的那個值 要放進A23 那這算法跟他一樣 那這是B0個level 這是B1個level 所以是每次這個是兩次乘上0.2 加一次乘上0.1 這樣到0.5

那這個是一次乘上0.2 加兩次乘上0.1 看得到0.4 所以這個是0.4

對,平均視頻 所以這翻例3.8 那就舉個例子 那如果說今天我要算A23 那A23的狀況就是現在上面圖的樣子 就是2號點到3號 2號點跟3號點他們所組合成的翻例色指區的樣式 那目前有2 那1號點到3號點組合的樣式有5種 那2跟3組合的樣式有2種 有2種

那組合同學要留意一下 你要符合原則就是 你目前的節點的左側小一點的狀況 右側大一點的狀況 這個不能違反 這個原則不能違反 那為什麼要做這樣的鋪陳呢 就是我們要為什麼範地3.7 先叫你看一下A13 那剛才又問了你這個AII AII就是A1 A2 A2 A3 那翻譯3.8用問你A23 幹嘛要問那麼多次

那留意一下我們這個主題是動態規劃 那動態規劃的意義是什麼 我們把原始的大問題要先縮小 縮小之後我們用bundant out的方式要算回去 我們把原始大問題縮小 然後用bundant out的方式算回去 也就是說

可能原始問題是這一個 A13或許不是這樣算出來 我們剛剛只是 算是窮舉法 如果在數學裡面這叫窮舉法 所有可能都列出來 然後去看他的結果 但是我們真正算可能不是這樣算 我們真正算是怎樣 我們要算A13的時候 我們可能會算A1 可能會算A2 可能會算A33 我們可能會先算到這幾個東西 甚至我們可能也會先算到A23 我們可能會先算到A23

同學兩家解嗎 所以這是我們的最終答案 但是最終答案在出現之前 我們可能會先算出這些小答案出來 那這些小答案剛好就是這樣的一個組合形式 就是這樣的組合形式慢慢的堆積上來的 剛好符合我們動態規劃的一個運作原則 同學先看這邊

可以吗 那我们先休息一下

那我接下來要看下一頁 剛剛在講上面這一頁 那同學要有一個概念 最下面整個在最下面 Ai、J 如果以I跟J 就 DI的key 跟到J的key 那這樣的一個組合的二元搜尋 那個Bine Tree 它的一個最小的一個搜尋時間 會記在矩陣裡面Ai、J 的位置 所以我們剛才用範例 比如I4、J、J、J 就是三個key 1號到3號三個key 它的最小的平均搜尋時間 會記在A13的位置 但是要算A13之前 比如說動態規劃的一個做法 我們可能A1要先算 A22要先算 A33要先算 甚至剛才範例3.8 可能A23要先算 可能A12也要先算 類似這樣的一個概念 OK

好,那我們現在要把整個問題稍微再擴大一點 變成一個一般的一個形式 那我們要把他的那個矩陣的一個變化式要把它寫出來 我們那個bottomart的一個運作方式 然後再來就可以運用在我們的一個

DP的一個演算法裡面 那它現在畫一個簡單的示意圖 假設我們現在是 我們要算A1N 1號點到N號點 1號點到N號點 那它的一個大致上示意圖像這樣 假設我們的root是

K,PK,就是K號碟當作路 那1到N的話,大小就是照這個順號 1最小,N最大,這樣子 那假設現在K是路德的話 那左側就是1號到K-1 他直接稍微這樣畫一下 右側就是K+1到N 這樣符合他的左邊是小一個,右邊是大一個的一個狀況

同學先看這些問題 OK 那我們開始把問題做一個分割 因為動態規劃也要跟禮拜的堂口一樣要分割 所以假設我們分割的話 左邊這一半它的算法不就是 1號到K-1號 就是AEK 對不對 左側這一半

那右側這一半不就是AK+1N 如果在我們剛才的一個概念的話 所以整體 整個 整個全部是 最佳只會記錄在A1N的位置 所以值A1N的位置

整體會記在這個位置 那他假設說以目前的結構來看 中間上方Root這個是編號K 那左側就是1到K-0 右側就是K+1到0 符合他的一個基本的一個運作方式 那左側這邊所形成的一個指數 那他的最佳值會記在這個位置 對不對 右側這邊會記載這個位置 先看看這邊有沒有問題

整體是記憶在A1N的地方 那現在如果以畫面上這樣來分 左邊所形成的那個指數 它的最佳的一個search time 會記憶在A1K-1的地方 就所以是A1K-1的地方 那右側就是A1K+1N的地方 我先看這邊有問題

可以,那現在還有一堆散戶 就是P系列的這個散戶 我們先看中間這一位 這一位其實是他 這一位是他 因為他現在是 也不是左邊也不左,他是 root 所以經過他的時候會有一次的比較 對不對 那一次的話就是E*上 那他的機率值如果他有就是PK的話 那這機率值也是跟編號一起順號

KKE的機率值就是PE,那KE2的機率值就是PE,就跟著順號 所以目前這個KEKE的話,機率值就是PEK 那至少他就是root自己,所以一次 那這個比較沒問題,那現在左側右側都一樣

左側右側這個是算額外的部分 就是剛才左側是A1到K-1的組合 右側是K+1到2的組合 那怎麼又多了這些東西出來 那主要是左側1到K-1這個組合 這組合方式有各式各樣

就像我們剛才辦例3.7 比如說1號點到3號點組合的方式有很多種 就是每一個點都有可能當Loot 每一個點都有可能在最高的位置 在左側的最高位置 或是這邊每一個點都有可能在右側的最高位置 就在這邊 那如果以這樣來看的話 那它有如果1號點在最上面或2號點在最上面 3號點在最上面 脫子的最上面是這裡的最上面 左指數的最上面 那它就有額外的一個比較次數要去做記憶 因為在路程的話次數是隱式的

一次 所以就一乘上 他們各個的機率值 所以這邊是配合左指數的 這邊是配合右指數的 ok 那接下來我們把它稍微整理一下 那這裡 這個就直接寫下來 這個也直接寫下來 那這一段 這一個這一段 這三段合起來剛好變這樣 剛好變這樣

所以整個來說的話 在下面做一個統整 所以A1N的話 上面就是在算A1N 那就是如果我們寫比較正式一點 寫法就是這個樣子 那這邊有一個minima的動作 因為這邊的組合方式很多種 所以要取一個minima 要取一個minima 就這樣這邊跟這邊加起來 哪一個是最小的 那這一根後面這邊做加裝

這是最終我們要算的結果 是在整個矩正A1N的地方 A1N的地方 那我現在把它寫成通式的話 如果這邊E跟N換成IJ的話 那這邊用I跟J來替代 那這邊用I跟J來替代 那這邊用I跟J來替代 就變成這樣子

那這個是I小於J的時候 那如果I跟J一樣的 Ii的時候就是pi 前面我們上一頁有講 那還有兩種情況是B 就是I-1是B J+1J是B 還有這兩種情況是B

好,來先看這邊有沒有問題 那為什麼這兩種情況是你等一下我們用書上的辦理來跟同學做驗證 所以這是上面推導出來變這樣 那下面這三個是一個通式 他寫了一個通用的一個式子 用I跟J來替代I跟A

因為我們整體運算它要發展到它會從很下面很小的結果慢慢的累積上去 最後1N才會算出來 所以它現在用一個通四來線 用I跟J來線 然後接下來我們要看 等一下我們會看範例的3點 看多少嗎 3點9

那在看翻例3.9之前,我們先看一下它怎麼運作 這個演算法現在是這樣子 第一,有兩個後悔圈還蠻明顯的 有兩個蠻明顯的後悔圈 不過這個演算法我可以先問各位的小問題 它的時間複雜度是N38

前面這怎麼推倒就算了 我們就看這個N三方 那我有提過動態規劃裡面 它其實是看回軒的層數 看回軒的層數 N三方的話表示是三層回軒 三層回軒 那先各位看一下 這個例子那第三層在哪

這個例子的第三層代 這是第一層 這是第二層 你說第三層代上面F不是 那只是做一個initial的動作 第一層代這個第二層代這個第三層代 啊 可以嗎 同學看這個問題 第三層代這邊

這是這個minima的動作 你看它有I小一個K小一個Z 所以它是一個範圍 所以表示說這個動作它會做很多次 那做很多次之後它要取最小的 所以第一層在這 第二層在這 第三層在哪 這個minima 所以有算法同學要 就是跟程式的寫法稍微不太一樣 有算法可以這樣寫 但是你程式沒辦法直接寫一個minima 你沒辦法 你要自己還是自己要去實作出來 但是在演算法裡面 一層兩層第三層就在打 所以它會23方 可能是這個樣子

好 那同學先看這邊有問題

對嗎? 好 好,第一個有最大問題解決 所以時間複雜度其實 第三張時間複雜度都很好分期 就是看回圈陳述就好 所以解決了 再來就是,那這個回圈它怎麼好 這個回圈有一個很重要的一個

他把這個單字當成他比較好的一個方式 叫Dagono 知道他什麼嗎? 有學過嗎? 那個線性代數你學了嗎? 現在裡面應該都有在那個正列裡面 Dagono是對角線的意思

也就是說等一下他的回軒的一個運作方式跟對角線有關 不是橫向也不是縱向是這樣子 那等一下跑的方式是這樣跑 這樣跑對角線跑 那擺動龍1從對角線1號對角線開始跑 然後慢慢的做工作

還有代工人家將 那下一條對角線在哪邊 等一下我們用範例來告訴各位 我們現在要看範例3.9 一樣我沒有把它放在獎勵上 所以我要先寫一下文天版

好

好

差不多就這樣了 這是範例3.9 範例3.9 範例3.9的話 他就馬上就給各位答案 就這個我要算出A矩陣 那我們最終答案在哪裡 在這個位置

因為現在這個題目才有四個節點 那四個節點它上面是用英文字 所以等一下用DIRW來做一個大小的區分 那其實我們直接用編號也可以 我們就直接把它當成KEY1234 那就以1234的順 然後這樣也OK也比較順 那我們最終的答案在這個地方A14 我們主要算出A14出來 但是在算A14之前有很多要先算 因為動態規劃的運作 我們都要先算 那我們先看一下哪邊我們可以先填 這個可以先填

這個矩陣有一點特別 我們要看一下 A矩陣 I的順號是 就是 12345 I的順號 J的順號是01234 所以他的那個順號不一樣 I是從1開始 J是從0開始

可以嗎? 這個可以先做 你可以看一下 比如SE的時候 就是1然後1-1 10 對不對?10的位置是0 先一口氣寫下來 它有幾個地方是0 等於是 以目前來說 這一條對角線是0

那為什麼二一的位置是0帶進去2 I是2 2-1 沒錯 21是0 I是3 3-1 3-2也是0 4-3是0 5-4是0 對 有點歪掉了

OK 好,所以這邊先出來 那第二個可以出來的是這個 AII是PI AII在哪裡? 這裡 AEE是PI 這個是那個機率值 對,這邊是8分之3 A228分之3 A33就是P3,8分之1

這邊可以嗎?先看這裡,這兩個可以先補出來

那接下來他的運作方式 先標記給各位 他的運作方式現在是這樣子 他是以對角線方式的來運作 所以他其實一開始是先處理這個 第二次是處理這個 第一次是這樣 那第三次是這樣 所以接下來你要處理的是A12

然後接下來是以對角線來看 你要除以的是A23 然後接下來你要除以的是A34

順序上是這樣子 標記一下 1 2 3 然後接下來是他 A13 然後接下來是他 A24

那最後才是A14 這個是最後 所以這邊的數以順序是依照對角線 所以他最先放的是這個 初始始 然後再來是這個 再來就是這一條對角線 123 然後再這個 40 然後最後是這個

所以同學在算這一題的時候 我要看到的是 你要以對角線的順序計算 了解嗎 你要以對角線的順序去計算你的字 你不是橫的算 也不是重的算

你要以對角線的順序計算這一題的內容 這個很重要

我們無問題,先這樣子 那接下來的A1223341324跟A14全部用的公式就是 就是使用它

我問你 我問你

那書上的話 這一題書上就題目 題目答案 那就全部算給你了 然後過程沒有 這本書厲害的地方就是從我們前幾章看到 題目馬上就答案 過程中

這本書就是他比較奇妙的一個地方 過程就要靠老師在上面講 來就照那個 我先寫比較完整 比如說這是1小語 等於A小語等於2 對不對 所以是A

黑衣服

好,那你先看到这有什么问题 好,那接下来这个迷你码 K41的时候是 这个是A K41的时候是A10 加上 A22

還有在是K12的時候 K12的時候 是 A 加上 A32

A10現在是0 這個是0 A22現在是0

A32現在是0 好,所以兩邊都可以,因為都是8分之三 那這個是8分之三加8,這是8分之六 對不對 所以現在這邊,前面這邊他也可以 因為這是8分之三,後面這也是8分之三 所以兩個都是最小的,所以OK 所以等於是8分之三加後面的8分之六 就8分之九,所以

這一個是八分子 好 第一格出來對不對 對滿好的 沒有錯 來這有沒有問題 那同樣的A23 然後A

3 4 接下來你要算的是他 你要算的是他 不是這一個 所以你要1 2 3 4 6 要照這個順序算 再次強調 這個順序很重要

好,我們先看這個,我們先算AE2

假设依照这个算法 你可以继续把A23跟A23

算出來,對不對? 那我直接看一下答案 這個是一個是八分柱,一個是八分之三 同樣的方式,這個可以算出八分之五 這個可以算出八分之三 這個會是 就照上面的一個運作 那這邊等於是二三的話,就是二到三 三四的話,就是三到四 這邊也是一樣二到三,然後三到四

然後我們現在分別去找 那我們現在再多提供一個 假設我現在算算算這三個都算完了 那我現在就可以算A13

前面那個對角線是它的mini碼 它的mini碼裡面只有兩個選項在選嘛 前面這個算是跟後面這個算是 那接下來這一組對角線mini碼裡面會有三個選項 所以 1小遠k 小遠3

就這樣子 對不對 那這邊 我就再把它細寫出來 這三個分別是 然後後面這個是P、P2、P3相加 那前面是A10+A13 10是0

是10 自己 然後13是 不是13 抱歉 是23 A23是 23 八分之五 所以 剛好透過這個例子 這邊是A10 這個是A23 K是1 A23 所以如果說你的算法是 這個算完然後12算完就算13 那你這時候你沒有A23的答案 對不對

就你A23還沒出來就先算A13那就不對 所以他的順序是對角線 所以請同學留意的就是這個地方 如果說你是橫向 依照你以前算矩正的一個概念就橫向的算 那你A12算完馬上去算A13那會有問題 因為你當作會需要用到這個字 那這個字你還沒算出來

那接下來2的時候是1 1 1 1現在是3/8 然後2的時候是33 33現在是1/8 然後再3 1 2 1 2現在是9/8

然後3,43,43現在是0 所以這是哪一個?這一個 那這現在是3,3,8分之7 對不對?還好沒算錯 就8分之4,所以13是這樣下去吧

那我把整個答案寫上去 再來你會算A24 24現在是1 然後這個答案是4 對不對 最終答案是4分之7

就這樣 那我這邊舉兩個例子 一個是 第一個部分 一個是第四個部分

來,同學看這邊有問題 再次強調計算上的順序依照對角線 等於是斜著算 如果你不是斜著算的話 你會在過程中遇到一些你還沒算出來的值 那你這邊就會算不下去 所以是斜著算,這很重要 既然各位這一節都來了 只要比那些沒有來的不知道這麼酸

這個計算過程書上沒有 書上就是 如果你們手邊有那個 你們手邊應該都不是紙本書 看起來好像大家都提版 那不管怎樣 反正紙本書也好 電子書也好 它上面都沒有過程 就題目題目答案就這樣 那過程你要自己寫 要自己把它做出來 那比如說剛才這邊我沒有做的

這你就可以自己試算 還有比如說這個2.4你也可以算一下 那最後答案1.4你也可以算一下 看他怎麼算出來

那我們考試過程中,因為我們是職門考試,所以過程很重要 所以變成說你不是只有給我答案,過程 就我要看到你的過程 不過像這種提醒的話,你說每一個到業的過程好像還蠻辛苦的 那注意看我考試上、試卷上的規則 我也許只要你寫幾個過程就好 其他的你就可以在旁邊斷氣麻辣算這樣子

就是過程是要讓我知道你會做 所以比如說現在上面這123456 這六個共和假設他的計算方式都是雷同 那也許我只要你寫一個過程 所以要注意題目上的一個需求 可能不用每個都列出來 就是列幾個 但我知道你會算 後面你就可以用它 就可以在那個試卷子上面自己算 然後算完答案給上去