某一類的遞迴方程式 滿足以下形式 : 其中, 與 都是關於 的函數, 而不是關於 的函數. 除此之外, 為任意正整數, . 我們稱類似的 為線型遞迴方程式. 若 , 則 其遞迴深度未達到 , 不能稱為…
在貪婪演算法下, 若制定好貪婪準則, 並且在貪婪準則下作出抉擇之後, 無法對其結果進行更改, 即抉擇作出後無法撤回. 在動態規劃中, 我們需要考察一系列抉擇, 以確定一個最佳的抉擇序列下, 所有子序列…
使用分而治之演算法的思想, 可以實現另外一種排序法, 即快速排序法. 在快速排序法中, 首先將序列分為三個部分 : 左段、支點和右段. 支點是來自序列中的某一個元素, 其取法包括但不限於 : 取序列第…
對於合併排序法, 我們得到的時間複雜度遞迴方程式為 首先, 我們來討論為何 成立. 由於 中含有取整函數, 並不容易計算, 因此我們不妨限定 為整數, 於是有 當 時, 其操作的時間複雜度為常數級別,…
對於任意問題, 設其至少有一個複雜度為 的演算法, 那麼稱 是該問題複雜度的一個上界. 對於一個問題的複雜度上界 , 要想其成立, 那麼只需要針對這個問題設計一個複雜度為 的演算法即可. 但是對於該問…
在之前的文章中, 我們講述了分而治之演算法, 而它的思想可以被用於排序中. 這種排序法設計的整體思路為 : 令 是當前要排序的元素數量, 若 , 則演算法終結; 當 時, 電腦可以在瞬間通過交換來完成…
自從開始讀研究生, 這個博客的 level 就越來越高了... 首先要向大家介紹什麼是計算理論. 這是一個電腦科學的分支, 而且是完完全全理論性的一個研究分支. 我們都知道, 不管是硬體還是軟體, 它…
分而治之和貪婪演算法一樣, 也是一種演算法基本策略. 在使用了分而治之演算法的問題中, 我們通常通過遞迴來解決問題, 因為分而治之的思想本質上就是遞迴思想. 對於某一些問題, 我們通常採用這樣的策略 …
有 個物品和一個容量為 的背包, 從 個物品中選取裝包的物品, 第 件物品的重量為 . 價值為 (). 一個可行的背包裝載是裝包物品的總重量不超過背包的容量的 . 一個最佳背包裝載是指物品的總價值最高…
在文章《貪婪演算法》中, 我們已經講述了貪婪演算法和 NP 問題的定義. 今天, 我們要使用貪婪演算法來解決兩個問題 : 機器調度問題和箱櫃裝載問題 例 1. [任務排程] 一個工廠有 台機器, 工廠…

大家都搜尋

關注我們的微信官方帳號

微信官方帳號