tag:blogger.com,1999:blog-49499601816288882212024-03-13T20:44:35.106+08:00Infinite LoopAnonymoushttp://www.blogger.com/profile/17636157464310241832noreply@blogger.comBlogger169115tag:blogger.com,1999:blog-4949960181628888221.post-69142638162437479012010-09-19T14:18:00.006+08:002010-09-19T14:31:01.876+08:00【介紹】Code::Blocks 為了能撰寫 C/C++ 的程式,你可能需要在自己的電腦中建置一套 <a href="http://en.wikipedia.org/wiki/Integrated_development_environment">IDE(Integrated Development Environment,整合開發環境)</a>,卻又不想用需要付費、又只能在 Windows 上執行的 <a href="http://msdn.microsoft.com/zh-tw/vstudio/">Visual Studio</a>(雖然 VS 也有提供免費的 <a href="http://www.microsoft.com/express/Default.aspx">Express Edition</a>)。<br />
<span id="detail">
<br />
或許會有人推薦你使用 <a href="http://www.bloodshed.net/devcpp.html">Dev-C++</a> 這套 open source 的免費軟體。不過根據我自己使用過的經驗,Dev-C++ 時常在執行到一半的時候當掉。而且其最新版本 4.9.9.2 是在 2005 年 2 月發佈的,顯然已經好幾年都沒有在繼續更新。<br />
<br />
在這裡,我要為各位介紹另一款同樣免費又穩定的 IDE - <a href="http://www.codeblocks.org/">Code::Blocks</a>。<br />
<br />
<br />
Code::Blocks 是一個 open source 的 IDE。由於其是由 <a href="http://en.wikipedia.org/wiki/WxWidgets">wxWidgets</a> 寫成,因此也具備了跨多種平台(Windows、Mac OS X、Linux 等)的能力。<br />
<br />
Code::Blocks 也支援多種<a href="http://en.wikipedia.org/wiki/Compiler">編譯器(compiler)</a>,如常見的 <a href="http://en.wikipedia.org/wiki/GNU_Compiler_Collection">GCC</a> / <a href="http://en.wikipedia.org/wiki/MinGW">MinGW</a>、Microsoft 的 <a href="http://en.wikipedia.org/wiki/Visual_C%2B%2B">Visual C++</a>、Intel 的 <a href="http://en.wikipedia.org/wiki/Intel_C%2B%2B_Compiler">ICC</a> 等。除此之外,Code::Blocks 還支援匯入 Dev-C++ 與 Visual C++ 專案的能力,可謂功能相當豐富。<br />
<br />
<br />
在這裡簡單示範一下如何在 Windows (XP Pro SP3)下安裝 Code::Blocks。<br />
<br />
首先,先進到<a href="http://www.codeblocks.org/downloads/26">下載頁</a>,找到 Windows 用的 binary 版本。當前的最新版本為 10.05,提供了 <b>"codeblocks-10.05-setup.exe"</b> 與 <b>"codeblocks-10.05mingw-setup.exe"</b> 兩個安裝檔,分別為單純的 Code::Blocks 與包含 MinGW 的版本。<br />
<br />
在這裡,我選擇的是<b>不包含</b> MinGW 的版本。<br />
<br />
<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://1.bp.blogspot.com/_1111KAvK4Ds/TJWr6FNhONI/AAAAAAAABUM/Ij4cTXqKfnU/s1600/1.PNG"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 281px;" src="http://1.bp.blogspot.com/_1111KAvK4Ds/TJWr6FNhONI/AAAAAAAABUM/Ij4cTXqKfnU/s400/1.PNG" border="0" alt=""id="BLOGGER_PHOTO_ID_5518505932732053714" /></a>
<br />
下載完成、執行安裝檔後,會出現選擇安裝元件的畫面。基本上,遵照預設值,直接按 "Next" 即可。<br />
<br />
<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://3.bp.blogspot.com/_1111KAvK4Ds/TJWr6Z5iUlI/AAAAAAAABUU/_h38pf1MzG8/s1600/2.PNG"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 310px;" src="http://3.bp.blogspot.com/_1111KAvK4Ds/TJWr6Z5iUlI/AAAAAAAABUU/_h38pf1MzG8/s400/2.PNG" border="0" alt=""id="BLOGGER_PHOTO_ID_5518505938285384274" /></a>
<br />
接著選擇安裝的目錄。<br />
<br />
<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://4.bp.blogspot.com/_1111KAvK4Ds/TJWr6jKesnI/AAAAAAAABUc/lBEmrJGwy1M/s1600/3.PNG"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 310px;" src="http://4.bp.blogspot.com/_1111KAvK4Ds/TJWr6jKesnI/AAAAAAAABUc/lBEmrJGwy1M/s400/3.PNG" border="0" alt=""id="BLOGGER_PHOTO_ID_5518505940772369010" /></a>
<br />
接著就可以等待安裝完成了。<br />
<br />
<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://4.bp.blogspot.com/_1111KAvK4Ds/TJWr62GRjyI/AAAAAAAABUk/NMmBhgjsGh0/s1600/4.PNG"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 310px;" src="http://4.bp.blogspot.com/_1111KAvK4Ds/TJWr62GRjyI/AAAAAAAABUk/NMmBhgjsGh0/s400/4.PNG" border="0" alt=""id="BLOGGER_PHOTO_ID_5518505945855004450" /></a>
<br />
<br />
在 Code::Blocks 安裝完成之後,我們還需要安裝 MinGW 作為其使用的編譯環境。(假如在第一步下載的就是包含 MinGW,這一步可以跳過。當然,你也可以選擇 MinGW 以外的編譯環境,如 ICC。)<br />
<br />
MinGW 的安裝方式請參見<a href="http://program-lover.blogspot.com/2009/02/gcc-mingw.html">這篇</a>。<br />
<br />
<br />
第一次開啟 Code::Blocks 時,它會請你選擇一個預設的編譯器。後面有寫 <b>"Detected"</b> 的,代表 Code::Blocks 在你電腦偵測到的已安裝的編譯器。<br />
<br />
這裡我們選擇 <b>"GNU GCC Compiler"</b>。<br />
<br />
<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://1.bp.blogspot.com/_1111KAvK4Ds/TJWr7SqIJQI/AAAAAAAABUs/QGdM5pC_aqk/s1600/5.PNG"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 240px;" src="http://1.bp.blogspot.com/_1111KAvK4Ds/TJWr7SqIJQI/AAAAAAAABUs/QGdM5pC_aqk/s400/5.PNG" border="0" alt=""id="BLOGGER_PHOTO_ID_5518505953521575170" /></a>
<br />
安裝到這邊,就可以開始使用 Code::Block 了!<br />
<br />
<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://3.bp.blogspot.com/_1111KAvK4Ds/TJWsZjyNYYI/AAAAAAAABU0/PsVwN2xLpwk/s1600/6.PNG"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 280px;" src="http://3.bp.blogspot.com/_1111KAvK4Ds/TJWsZjyNYYI/AAAAAAAABU0/PsVwN2xLpwk/s400/6.PNG" border="0" alt=""id="BLOGGER_PHOTO_ID_5518506473514951042" /></a>
<br />
<br />
想利用 Code::Block 新增一個 C/C++ 的檔案,請點選選單的 <b>File > New > File...</b>。<br />
<br />
<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://1.bp.blogspot.com/_1111KAvK4Ds/TJWsZ-8WE7I/AAAAAAAABU8/FvC6v3w1fBI/s1600/7.PNG"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 280px;" src="http://1.bp.blogspot.com/_1111KAvK4Ds/TJWsZ-8WE7I/AAAAAAAABU8/FvC6v3w1fBI/s400/7.PNG" border="0" alt=""id="BLOGGER_PHOTO_ID_5518506480805221298" /></a>
<br />
接著選擇 <b>"C/C++ source"</b>。<br />
<br />
<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://2.bp.blogspot.com/_1111KAvK4Ds/TJWsaH5yWCI/AAAAAAAABVE/6P8ncSzuKnA/s1600/8.PNG"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 298px;" src="http://2.bp.blogspot.com/_1111KAvK4Ds/TJWsaH5yWCI/AAAAAAAABVE/6P8ncSzuKnA/s400/8.PNG" border="0" alt=""id="BLOGGER_PHOTO_ID_5518506483210410018" /></a>
<br />
然後選擇 <b>"C"</b> 或 <b>"C++"</b>。<br />
<br />
<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://4.bp.blogspot.com/_1111KAvK4Ds/TJWsaRzHBGI/AAAAAAAABVM/tLwilHk0V1c/s1600/9.PNG"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 319px;" src="http://4.bp.blogspot.com/_1111KAvK4Ds/TJWsaRzHBGI/AAAAAAAABVM/tLwilHk0V1c/s400/9.PNG" border="0" alt=""id="BLOGGER_PHOTO_ID_5518506485866759266" /></a>
<br />
並設定檔案建立的路徑。<br />
<br />
<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://2.bp.blogspot.com/_1111KAvK4Ds/TJWsaseMO1I/AAAAAAAABVU/XdoTbVdARJA/s1600/10.PNG"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 319px;" src="http://2.bp.blogspot.com/_1111KAvK4Ds/TJWsaseMO1I/AAAAAAAABVU/XdoTbVdARJA/s400/10.PNG" border="0" alt=""id="BLOGGER_PHOTO_ID_5518506493026777938" /></a>
<br />
撰寫完程式,再按下工具列的 <b>"Run"</b> 就可以編譯執行了。<br />
<br />
<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://3.bp.blogspot.com/_1111KAvK4Ds/TJWtGISbjWI/AAAAAAAABVc/dOl_kNd6Zzw/s1600/11.PNG"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 400px; height: 280px;" src="http://3.bp.blogspot.com/_1111KAvK4Ds/TJWtGISbjWI/AAAAAAAABVc/dOl_kNd6Zzw/s400/11.PNG" border="0" alt=""id="BLOGGER_PHOTO_ID_5518507239228018018" /></a>
<br />
<blockquote>
Reference:
<ul>
<li><a href="http://www.codeblocks.org/">Code::Blocks</a></li>
<li><a href="http://en.wikipedia.org/wiki/Code::Blocks">Code::Blocks - Wikipedia</a></li>
<li><a href="http://c9s.blogspot.com/2007/07/visual-c-tutorial.html">Writing C++ Application Without Visual C++</a></li>
</ul>
</blockquote>
</span>Anonymoushttp://www.blogger.com/profile/17636157464310241832noreply@blogger.com4tag:blogger.com,1999:blog-4949960181628888221.post-40821988110959807592010-09-15T00:34:00.008+08:002010-09-15T00:52:24.068+08:00【雜記】漫談樹狀結構 在之前寫的「<a href="http://program-lover.blogspot.com/2008/12/tree.html">樹(tree)</a>」這篇文章中,有網友提到:希望能夠瞭解 tree 能夠在應用上什麼問題上面。不過,由於我本身對樹的瞭解也很粗淺,所以這篇就野人獻曝一下,隨意講講一些我知道的東西。學得不甚透徹,可能會有些不完整或是錯誤的地方,就請各位別見怪囉 :P<br />
<span id="detail">
<br />
<br />
先前曾經提到:在樹狀結構中,<b>節點(node)</b>的<b>分支度(degree)</b>代表其子節點(child)數量。若是有一種樹狀結構至多只會有 n 個子節點,即樹中的任何節點分支度均小於或等於 n,則我們會將這種樹稱為一棵「<b>n 元樹</b>」。<br />
<br />
其中,大概就屬<b><a href="http://en.wikipedia.org/wiki/Binary_tree">二元樹(binary tree)</a></b>的應用最為廣泛。如上所述,其節點至多只會有兩個子節點。通常我們會直接將之稱為<b>左子(left child)</b>與<b>右子(right child)</b>。下圖是一棵二元樹:<br />
<br />
<center><a href="http://en.wikipedia.org/wiki/File:Sorted_binary_tree.svg"><img src="http://upload.wikimedia.org/wikipedia/commons/6/67/Sorted_binary_tree.svg" /></a></center><br />
<br />
<br />
在談應用之前,讓我們先來看看一個樹狀結構常見的操作:<b><a href="http://en.wikipedia.org/wiki/Tree_traversal">尋訪(traversal)</a></b>,也就是依照某種順序訪問樹中的所有節點。一般來說,常見的尋訪方式包含<b><a href="http://en.wikipedia.org/wiki/Depth-first_search">深度優先尋訪(depth-first traversal)</a></b>與<b><a href="http://en.wikipedia.org/wiki/Breadth-first_traversal">廣度優先尋訪(breadth-first traversal)</a></b>。<br />
<br />
以上面的樹狀圖來說明,深度優先尋訪會先從根節點 F 開始,走訪 F 的第一個子節點 B,再接著走訪 B 的第一個子節點 A。由於 A 不具有子節點,所以我們退回上一層,再接著走訪 B 的第二個子節點 D。完整的尋訪順序為:F B A D C E G I H。<br />
<br />
而廣度優先尋訪相對於深度優先尋訪的不斷深入,是以<b>層級順序(level-order)</b>來進行尋訪。所以同樣由根節點 F 開始,走訪 F 的第一個子節點 B,再接著走訪 F 的第二個子節點 G。由於 F 只有兩個子節點,所以我們接著尋訪下一層 B 的子節點 A 與 D,然後是 G 的子節點 I。完整的尋訪順序為:F B G A D I C E H。<br />
<br />
<br />
其中,二元樹又具有三種特殊的尋訪方式:<b>前序(pre-order)</b>、<b>中序(in-order)</b>、與<b>後序(post-order)</b>。若是把尋訪根節點、尋訪左子樹、尋訪右子樹分別記做 D、L、R,則前序的尋訪順序為 D L R、中序的尋訪順序為 L D R、後序的尋訪順序為 L R D。<br />
<br />
以同樣的圖舉例的話,前序的尋訪順序為:F B A D C E G I H、中序的尋訪順序為:A B C D E F G H I、後序的尋訪順序為:A C E D B H I G F。(正確來說,二元樹只比一般的樹多了中序與後序兩種尋訪方式,因為前序尋訪與深度優先尋訪的順序其實是相同的。)<br />
<br />
<br />
說完了尋訪,不過跟應用有什麼關聯呢?其中一個常見的用途是<b>排序(sorting)</b>。<br />
<br />
我們可以定義一個特殊的二元樹:樹狀結構中,其左子樹所有節點所存的值必定小於根節點的值,且其右子樹所有節點所存的值必定大於等於根節點的值。如下圖:<br />
<br />
<center><a href="http://en.wikipedia.org/wiki/File:Binary_search_tree.svg"><img src="http://upload.wikimedia.org/wikipedia/commons/d/da/Binary_search_tree.svg" /></a></center><br />
<br />
有沒有發現,當我們用中序來尋訪這棵二元樹,我們便可以得到一個升序(ascending order)的數列。<br />
<br />
<br />
若是根據定義,給出一個新增節點的操作:<br />
<br />
<pre class="code">
Function insertNode(TreeNode root, Type value)
If root.value > value then
If root.hasLeftChild Then
insertNode(root.leftChild, value)
Else
root.leftChild = CreateNode(value)
Else
If root.hasRightChild Then
insertNode(root.rightChild, value)
Else
root.rightChild = CreateNode(value)
End
</pre>
<br />
利用這個新增節點的操作,我們便可以將一堆資料建立成一棵符合定義的二元樹。於是,我們便可以利用這個操作,在加上中序尋訪來得到一串排序過的資料。<br />
<br />
<br />
事實上,這種特殊的二元樹,被稱為<b><a href="http://en.wikipedia.org/wiki/Binary_search_tree">二元搜尋樹(binary search tree)</a></b>。其義如其名,這種二元樹也可以用以進行「已排序資料」的搜尋(search)。<br />
<br />
根據定義我們可以得知:若是欲尋找的值小於二元搜尋樹的根節點,則其右子樹必定不可能出現欲尋找的值;同樣的,若是欲尋找的值大於二元搜尋樹的根節點,則其左子樹必定不可能出現欲尋找的值。而這種方式其實就跟<b><a href="http://program-lover.blogspot.com/2008/08/binary-search.html">二分搜尋法(binary search)</a></b>的原理有異曲同工之妙。<br />
<br />
我們可以定義搜尋的操作如下:<br />
<br />
<pre class="code">
Function search(TreeNode root, Type value)
If root.value = value then
print "Found"
Else If root.value > value then
If root.hasLeftChild Then
search(root.leftChild, value)
Else
print "Not Found"
Else
If root.hasRightChild Then
search(root.rightChild, value)
Else
print "Not Found"
End
</pre>
<br />
而這種利用二元搜尋樹的搜尋方式,其複雜度為 <b>O(h)</b>。其中 h 為樹的高度(height)。而若每棵子樹的左右子樹節點數量都相同(或差一),則 h 即等同於 lg n,也就是說搜尋的複雜度為 <b>O(lg n)</b>,與二分搜尋法相當。<br />
<br />
<br />
由以上這些例子,可以知道「樹」不僅可以用來處理常見的排序與搜尋問題,還是種挺有效率的方式呢。<br />
<br />
<br />
<blockquote>
References:<br />
<ul>
<li><a href="http://en.wikipedia.org/wiki/Tree_(data_structure)">Tree (data structure) - Wikipedia</a></li>
<li><a href="http://en.wikipedia.org/wiki/Binary_tree">Binary tree - Wikipedia</a></li>
<li><a href="http://en.wikipedia.org/wiki/Tree_traversal">Tree traversal - Wikipedia</a></li>
<li><a href="http://en.wikipedia.org/wiki/Binary_search_tree">Binary search tree - Wikipedia</a></li>
<li><a href="http://www.csie.ntnu.edu.tw/~u91029/Tree.html">Tree - 演算法筆記</a></li>
<li><a href="http://mmdays.com/2008/01/19/data_structure_tree/">由樹的前序、中序、後序走法來談資料結構 - MMDays</a></li>
<li><a href="http://mmdays.com/2008/03/16/tree_sort/">二元樹在排序的應用 - MMDays</a></li>
<li><a href="http://mmdays.com/2008/03/29/tree_search/">二元樹排序對搜尋的影響 - MMDays</a></li>
</ul>
</blockquote>
</span>Anonymoushttp://www.blogger.com/profile/17636157464310241832noreply@blogger.com1tag:blogger.com,1999:blog-4949960181628888221.post-80867302656570590592010-07-23T21:46:00.003+08:002010-07-23T21:49:38.485+08:00【轉貼】Visualization of Quick sort 偶然在網路上看到的影片:用動畫展示<a href="http://program-lover.blogspot.com/2008/06/bubble-sort_20.html">氣泡排序法(Bubble Sort)</a>跟<a href="http://program-lover.blogspot.com/2008/11/quicksort.html">快速排序法(Quicksort)</a>的運作原理,並比較兩者的效率(進行比較的次數)。整支影片看起來還滿可愛的。<br />
<span id="detail">
<br />
<object width="480" height="385"><param name="movie" value="http://www.youtube.com/v/vxENKlcs2Tw&hl=zh_TW&fs=1"></param><param name="allowFullScreen" value="true"></param><param name="allowscriptaccess" value="always"></param><embed src="http://www.youtube.com/v/vxENKlcs2Tw&hl=zh_TW&fs=1" type="application/x-shockwave-flash" allowscriptaccess="always" allowfullscreen="true" width="480" height="385"></embed></object><br />
<br />
<a href="http://www.youtube.com/watch?v=vxENKlcs2Tw">Visualization of Quick sort</a>
</span>Anonymoushttp://www.blogger.com/profile/17636157464310241832noreply@blogger.com2tag:blogger.com,1999:blog-4949960181628888221.post-42197199460084198212010-07-11T12:21:00.009+08:002010-07-11T12:58:08.183+08:00【雜記】FLOLAC '10 <a href="http://flolac.iis.sinica.edu.tw/flolac10/">2010 Formosan Summer School on Logic, Language, and Computation(FLOLAC ’10)</a>,是辦在台大進修推廣部的暑期碩士學分班。雖然是碩士學分班,但由於剛好符合相關學系大二以上的報名資格,又在半自願被網友 yen3 「騙來」的狀態下還是報名了XD。<br />
<span id="detail">
<br />
<center><a href="http://lh3.ggpht.com/_1111KAvK4Ds/TDlFFOA9bAI/AAAAAAAABR8/AUtFqChYfNk/FLOAC2010-Poster-final.jpg"><img src="http://lh3.ggpht.com/_1111KAvK4Ds/TDlFFOA9bAI/AAAAAAAABR8/AUtFqChYfNk/s800/FLOAC2010-Poster-final.jpg" width="500" /></a></center>
<br />
<br />
<br />
對於一個語言,我們可以從兩個觀點來看它:一個是語法(syntax),即語言本身的規則(rule)與形式(form);另一個則是語意(semantics),為語言本身所表達的意義(meaning)。<br />
<br />
寫出可以執行的程式也許不難,要寫出正確的程式卻不簡單。當我們得到一段程式,我們該如何分析、驗證這個程式的結果,以確保其確實符合我們的預期?更甚者,我們該如何在撰寫程式的同時,也確保我們建構出來的程式一定是正確的?<br />
<br />
對於程式語法上的錯誤(syntax error)可以經由編譯器(compiler)或直譯器(interpreter)來幫我們檢查出來。但是,語意上的錯誤(logic error 或稱 semantic error)卻難以經由其他工具來協助我們察覺。<br />
<br />
一般我們也許習慣利用測試資料來確認程式的正確性:只要程式能通過所有的測試資料(即輸出結果符合預期),我們就可以「假設」程式是正確的了。不過,要產出全面性的測試資料本身有其難度,再加上此種方式必須仰賴於程式的實作(implement),作為驗證並不是一種非常好的方式。<br />
<br />
而 FLOLAC '10 這一系列的課程,主要的內容就是教導如何以邏輯推理為基礎,從語意的角度將程式形式化(formalize)並進行分析。以及用以輔助的 Frama-C 分析工具的使用。<br />
<br />
<br />
<br />
不過 FLOLAC ’10 的時程有兩天跟期末考撞期,所以一開始就請了兩天假。直到第三天的 Logic 跟 Op 課都已經是第二堂課,FP 課甚至已經結束了。要在沒聽過第一堂課的情況下銜接上內容,一開始還真是一個頭兩個大。還好後來漸漸跟上了,總算有種進入狀況的感覺。<br />
<br />
歷經了兩週八點準時起床出門上課,直到下午五點下課,比暑假前還規律的暑假生活,水深火熱的 FLOLAC '10 終於順利結束了。雖然課程有點辛苦,不過接觸了不少人、也接觸了不少新東西,感覺收獲也相當多。<br />
<br />
遇見了 yen3、GSR、dryman,還有其他周圍的人、努力想搞懂 Frama-C 到底在做什麼、跟 dryman 一起到麥當勞邊念書邊聊天、期末考前在 Google Wave 上熱烈的討論。對於整個 FLOLAC 的課程,我想我還滿樂在其中的。<br />
<br />
<center><a href="http://lh3.ggpht.com/_1111KAvK4Ds/TDlFL5rauBI/AAAAAAAABSE/zAMtFi2hHAI/FLOLAC.JPG"><img src="http://lh3.ggpht.com/_1111KAvK4Ds/TDlFL5rauBI/AAAAAAAABSE/zAMtFi2hHAI/s400/FLOLAC.JPG" /></a></center>
<br />
雖然不知道自己能學到多少,又能應用多少。不過也許就像 yen3 所說:「能體會,就能產生質變」。或許在之後就會發現,現在學過的這些,其實都有潛移默化的作用也說不定。
</span>Anonymoushttp://www.blogger.com/profile/17636157464310241832noreply@blogger.com2tag:blogger.com,1999:blog-4949960181628888221.post-40497366357544832842010-04-11T12:06:00.001+08:002011-10-27T16:03:45.076+08:00【演算】插入排序法 - Insertion Sort <a href="http://en.wikipedia.org/wiki/Insertion_sort"><b>插入排序法(insertion sort)</b></a>與<a href="http://en.wikipedia.org/wiki/Selection_sort">選擇排序法(selection sort)</a>類似,同為較簡易、直觀的<a href="http://en.wikipedia.org/wiki/Sorting_algorithm">排序演算法(sorting algorithm)</a>。其原理都是將資料分為「已排序」與「未排序」兩個部份。再將未排序資料中的第一筆資料插入到已排序資料的適當位置。<br />
<span id="detail"> <br />
<br />
<br />
與選擇排序法相同,一般我們習慣將「已排序」的資料擺在資料序列的前端,並將「未排序」的資料擺在資料序列的後端。<br />
<br />
若是我們需要將資料由小排到大。則我們會依序取出每個「未排序」的資料,然後由「已排序」資料的最後一筆開始,往前依序尋找第一個比這筆「未排序」資料還小的元素,並將其後的所有資料往後移一格,再將這筆「未排序」資料「插入」在這個「空出來的位子」。<br />
<br />
<br />
<br />
其虛擬碼如下:<br />
<br />
<pre class="code">Function insertionSort(Type data[1..n])
Index i, j;
Type value;
For i from 2 to n do
value = data[i];
j = i - 1;
While j >= 1 and data[j] > value do
data[j + 1] = data[j];
j = j - 1;
data[j + 1] = value;
End
</pre><br />
<br />
<br />
讓我們看看實際操作的例子。若是我們需要將以下資料由小排到大:<br />
<br />
<blockquote>83 31 96 17 42 14 54 </blockquote><br />
則每一次迴圈的執行結果如下:<br />
<br />
<blockquote><font color="red"><b>83</b></font> 31 96 17 42 14 54 </blockquote><br />
<blockquote><font color="red"><b>31</b></font> <font color="green">83</font> 96 17 42 14 54 </blockquote><br />
<blockquote><font color="green">31 83</font> <font color="red"><b>96</b></font> 17 42 14 54 </blockquote><br />
<blockquote><font color="red"><b>17</b></font> <font color="green">31 83 96</font> 42 14 54 </blockquote><br />
<blockquote><font color="green">17 31</font> <font color="red"><b>42</b></font> <font color="green">83 96</font> 14 54 </blockquote><br />
<blockquote><font color="red"><b>14</b></font> <font color="green">17 31 42 83 96</font> 54 </blockquote><br />
<blockquote><font color="green">14 17 31 42</font> <font color="red"><b>54</b></font> <font color="green">83 96</font> </blockquote><br />
<br />
<br />
同樣的,我們必須要分析這種演算法的執行效率如何。<br />
<br />
在資料都已排序的最佳情況下,資料大小為 n 的敘述執行次數如下:<br />
<br />
<pre class="code">Function insertionSort(Type data[1..n])
Index i, j; // 1
Type value; // 1
For i from 2 to n do // n - 1
value = data[i]; // n - 1
j = i - 1; // n - 1
While j >= 1 and data[j] > value do // n - 1
data[j + 1] = data[j]; // 0
j = j - 1; // 0
data[j + 1] = value; // n - 1
End
</pre><br />
敘述的執行次數總和:B(n) = 1 + 1 + (n - 1) + (n - 1) + (n - 1) + (n - 1) + (n - 1) = 5n - 3 ∈ Ο(n)。複雜度為線性時間。<br />
<br />
<br />
<br />
但是在資料完全反序的最差情況(註1):<br />
<br />
<pre class="code">Function insertionSort(Type data[1..n])
Index i, j; // 1
Type value; // 1
For i from 2 to n do // n - 1
value = data[i]; // n - 1
j = i - 1; // n - 1
While j >= 1 and data[j] > value do // n(n - 1) / 2
data[j + 1] = data[j]; // n(n - 1) / 2
j = j - 1; // n(n - 1) / 2
data[j + 1] = value; // n - 1
End
</pre><br />
敘述的執行次數總和:W(n) = 1 + 1 + (n - 1) + (n - 1) + (n - 1) + n(n - 1) / 2 + n(n - 1) / 2 + n(n - 1) / 2 + (n - 1) = (3n<sup>2</sup> + 3n - 4) / 2 ∈ Ο(n<sup>2</sup>),複雜度為平方時間。<br />
<br />
平均來說,這種演算法的執行效率並不算高,因此也比較不適合用以處理數量較多的資料。<br />
<br />
<br />
<blockquote>註1. 其中的 n(n - 1) / 2 是由 (n - 1) + (n - 2) + (n - 3) + ... + 1 加總化簡而來。 </blockquote></span>Anonymoushttp://www.blogger.com/profile/17636157464310241832noreply@blogger.com4tag:blogger.com,1999:blog-4949960181628888221.post-12731253342380309322010-04-10T15:23:00.009+08:002010-04-10T16:27:18.220+08:00【演算】合併排序法 - Mergesort <a href="http://en.wikipedia.org/wiki/Merge_sort"><b>合併排序法(mergesort)</b></a>是一個典型利用<a href="http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm">分治法(divide and conquer,D&C)</a>解決問題的例子。其原理為不斷地將資料分成兩等分,直到每份的資料量小到一個程度後,各自排序後再一一合併起來。<br />
<span id="detail">
<br />
<br />
<br />
假設現在有 n 筆資料需要進行排序。<br />
<br />
則我們首先會將這 n 筆資料分成兩等分(大小皆為 n/2);接著,再將這兩堆大小為 n/2 的資料各自分為兩等分(大小皆為 n/4);同樣的,我們再將這四堆大小為 n/4 的資料各自分為兩等分(大小皆為 n/8)。<br />
<br />
如此進行下去,直到每堆的資料量足夠小(例如:每堆只剩 1 筆資料)之後,我們就分別將每堆資料進行排序,再將這些資料堆兩兩一對進行合併,直到排序完成為止。<br />
<br />
<center>
<a href="http://en.wikipedia.org/wiki/Image:Merge_sort_algorithm_diagram.svg"><img src="http://upload.wikimedia.org/wikipedia/commons/thumb/e/e6/Merge_sort_algorithm_diagram.svg/618px-Merge_sort_algorithm_diagram.svg.png" width="520" /></a><br />
</center>
<br />
<br />
<br />
其虛擬碼大致如下:<br />
<br />
<pre class="code">
Function mergeSort(Type data[1..n])
If n <= 1 then return
Index x, y, i, j
x = n / 2
y = n - x
Type left[1..x], right[1..y]
For i from 1 to x do
left[i] = data[i]
For i from 1 to y do
right[i] = data[x + i]
mergeSort(left)
mergeSort(right)
merge(data, left, right)
End
Function merge(Type data[1..n], Type left[1..x], Type right[1..y])
Index i, j, k
i = j = k = 1
While i <= x and j <= y do
If left[i] < right[j] then
data[k] = left[i]
i = i + 1
Else
data[k] = right[j]
j = j + 1
k = k + 1
While i <= x do
data[k] = left[i]
i = i + 1
k = k + 1
While j <= y do
data[k] = right[j]
j = j + 1
k = k + 1
End
</pre>
<br />
<br />
<br />
讓我們舉個實際的例子說明:現在我們有八筆資料需要排序(由小而大):<br />
<br />
<blockquote>
(84、13、73、26、32、19、91、38)
</blockquote>
<br />
且只要每堆的資料量大於 1 時,就需要再將資料進行分割。<br />
<br />
首先,我們先將資料分成兩等分:<br />
<br />
<blockquote>
(84、13、73、26) (32、19、91、38)
</blockquote>
<br />
此時每堆的資料量為 4 (8 / 2) > 1。因此,我們還需要將每堆資料再各自分成兩等分:<br />
<br />
<blockquote>
(84、13) (73、26) (32、19) (91、38)
</blockquote>
<br />
此時每堆的資料量為 2 (4 / 2) > 1。再一次,我們將每堆資料各自分成兩等分:<br />
<br />
<blockquote>
(13) (84) (26) (73) (19) (32) (38) (91)
</blockquote>
<br />
此時每堆的資料量為 1 (2 / 2) = 1 ,符合停止切割的條件。所以接下來,我們要將資料兩兩合併。在合併的同時,同時確保資料排序:<br />
<br />
<blockquote>
(13、84) (26、73) (19、32) (38、91)
</blockquote>
<br />
同樣的,我們將資料兩兩合併:<br />
<br />
<blockquote>
(13、26、73、84) (19、32、38、91)
</blockquote>
<br />
同樣的,我們將資料兩兩合併:<br />
<br />
<blockquote>
(13、19、26、32、38、73、84、91)
</blockquote>
<br />
<br />
<br />
最後,我們從時間效率上來討論合併排序法。設 merge sort 的時間複雜度函數為 T(n)。<br />
<br />
我們可以知道,在每一次呼叫 mergeSort() 函式時,我們都需要分別將前半段與後半段的資料複製給 left 跟 right,所以複製資料的時間花費為 c<sub>1</sub>n。<br />
<br />
然後,我們需要遞迴呼叫兩次資料大小為 n/2 的 mergeSort(),時間花費為 2T(n / 2)。最後再加上呼叫 merge() 函式所需的時間花費 c<sub>2</sub>n。所以我們可以得到:T(n) = 2T(n / 2) + cn (n > 1),且 T(1) = 1。<br />
<br />
<br />
<br />
若是將式子展開:T(n) = 2T(n / 2) + cn = 4T(n / 4) + 2c(n / 2) + cn = 8T(n / 8) + 4c(n / 4) + 2c(n / 2) + cn = ... = cn + cn + cn + ... + cn = cn(lg n + 1) ∈ <b>O(n lg n)</b>(註1)。<br />
<br />
由此可見,合併排序的的時間效率是相當不錯的。<br />
<br />
<br />
<br />
另外,因為有網友詢問非遞迴的合併排序法,因此試著寫了以下這個虛擬碼:<br />
<br />
<pre class="code">
Function mergeSort(Type data[1..n])
If n <= 1 then return
Index i, j, k
For i from 2 to (n / 2) do
For j from 0 to (n - 1) step (2 * i) do
Index x, y
x = min(i, n - j)
y = min(i, max(0, n - i - j))
Type left[1..x], right[1..y]
For k from 1 to x do
left[k] = data[j + k]
For k from 1 to y do
right[k] = data[i + j + k]
Index p, q, r
p = q = 1
r = j
While p <= x and q <= y do
If left[p] < right[q] then
data[r] = left[p]
p = p + 1
Else
data[r] = right[q]
q = q + 1
r = r + 1
While p <= x do
data[r] = left[p]
p = p + 1
r = r + 1
While q <= y do
data[r] = right[q]
q = q + 1
r = r + 1
End
</pre>
<br />
寫起來感覺不太直觀,如果有錯誤歡迎糾正我:)
<br />
<br />
<br />
註1. 其實可以直接利用<a href="http://en.wikipedia.org/wiki/Master_theorem">支配定理(Master theorem)</a>來求出複雜度 T(n)。
</span>Anonymoushttp://www.blogger.com/profile/17636157464310241832noreply@blogger.com12tag:blogger.com,1999:blog-4949960181628888221.post-39439297176117164542010-03-20T19:12:00.003+08:002010-03-21T13:55:27.192+08:00【演算】選擇排序法 - Selection Sort <a href="http://en.wikipedia.org/wiki/Selection_sort"><b>選擇排序法(selection sort)</b></a>為一種較直觀的<a href="http://en.wikipedia.org/wiki/Sorting_algorithm">排序演算法(sorting algorithm)</a>。其將資料分為「已排序」與「未排序」兩部份,並從「未排序」的資料中找出最大(最小)值,放入「已排序」資料的最後端。如是進行,直到排序結束(未排序資料為空)為止。<br />
<span id="detail">
<br />
<br />
<br />
一般來說,我們的作法是:將「已排序」的資料擺在資料序列的前端,並將「未排序」的資料擺在資料序列的後端。<br />
<br />
假設我們需要將 n 筆資料由大排到小。在起初,這 n 筆資料都是「未排序」的。於是,我們從這 n 筆資料取出其中的最大值,並將之放在「已排序」資料的最後端。換言之,就是將之與第一筆資料進行交換。<br />
<br />
接著,我們再從剩下的 n - 1 筆資料取出最大值,同樣放入「已排序」資料的最後端(與第二筆資料進行交換);再從剩下的 n - 2 筆資料取出最大值,放入「已排序」資料的最後端(與第三筆資料進行交換)。<br />
<br />
以此類推,直到沒有任何「未排序」的資料為止。<br />
<br />
<br />
<br />
選擇排序法的虛擬碼大致如下:<br />
<br />
<pre class="code">
Function selectionSort(Type data[1..n])
Index i, j, max
For i from 1 to n do
max = i
For j from i + 1 to n do
If data[j] > data[max] then
max = j
Exchange data[i] and data[max]
End
</pre>
<br />
<br />
<br />
舉例來說,若我們需要將以下資料由大排到小:<br />
<br />
<blockquote>
19 58 33 41 28 14 53 84
</blockquote>
<br />
則以此演算法運作的過程如下:<br />
<br />
<blockquote>
<font color="red"><b>84</b></font> 58 33 41 28 14 53 <b>19</b>
</blockquote>
<blockquote>
<font color="green">84</font> <font color="red"><b>58</b></font> 33 41 28 14 53 19
</blockquote>
<blockquote>
<font color="green">84 58</font> <font color="red"><b>53</b></font> 41 28 14 <b>33</b> 19
</blockquote>
<blockquote>
<font color="green">84 58 53</font> <font color="red"><b>41</b></font> 28 14 33 19
</blockquote>
<blockquote>
<font color="green">84 58 53 41</font> <font color="red"><b>33</b></font> 14 <b>28</b> 19
</blockquote>
<blockquote>
<font color="green">84 58 53 41 33</font> <font color="red"><b>28</b></font> <b>14</b> 19
</blockquote>
<blockquote>
<font color="green">84 58 53 41 33 28</font> <font color="red"><b>19</b></font> <b>14</b>
</blockquote>
<blockquote>
<font color="green">84 58 53 41 33 28 19</font> <font color="red"><b>14</b></font>
</blockquote>
<br />
<br />
<br />
若是我們分析在最差情況下(所有資料的順序剛好完全相反),使用選擇排序法將 n 筆資料排序的敘述執行次數(註1):<br />
<br />
<pre class="code">
Function selectionSort(Type data[1..n])
Index i, j, max // 1
For i from 1 to n do // n
max = i // n
For j from i + 1 to n do // n(n - 1) / 2
If data[j] > data[max] then // n(n - 1) / 2
max = j // n(n - 1) / 2
Exchange data[i] and data[max] // n
End
</pre>
<br />
<br />
<br />
經由以上,我們可以得到最差情況下,敘訴的執行次數總和:W(n) = 1 + n + n + n(n - 1) / 2 + n(n - 1) / 2 + n(n - 1) / 2 + n = (3n<sup>2</sup> + 3n - 2) / 2 ∈ Ο(n<sup>2</sup>)。<br />
<br />
由此可知,選擇排序法的時間複雜度與之前介紹過的<a href="http://program-lover.blogspot.com/2008/06/bubble-sort_20.html">氣泡排序法(bubble sort)</a>相當,同樣為效率不大優良的排序演算法。<br />
<br />
<br />
<blockquote>
註1. 其中的 n(n - 1) / 2 是由 (n - 1) + (n - 2) + (n - 3) + ... + 1 加總化簡而來。
</blockquote>
</span>Anonymoushttp://www.blogger.com/profile/17636157464310241832noreply@blogger.com5tag:blogger.com,1999:blog-4949960181628888221.post-19160141932483873222010-03-13T12:49:00.000+08:002010-03-13T12:49:24.918+08:00【目錄】Verilog<font color="red"><b>Verilog 相關一覽</b></font><br />
<span id="detail">
<br />
<br />
<font color="blue"><b>筆記</b></font><br />
<br />
‧<a href="http://program-lover.blogspot.com/2010/03/verilog-0.html">Introduction to Verilog</a><br />
‧<a href="http://program-lover.blogspot.com/2010/03/verilog-1_12.html">Quartus II Installation</a><br />
‧<a href="http://program-lover.blogspot.com/2010/03/verilog-module.html">Verilog Module</a><br />
‧<a href="http://program-lover.blogspot.com/2010/03/create-verilog-project.html">Create a Verilog Project</a>
</span>Anonymoushttp://www.blogger.com/profile/17636157464310241832noreply@blogger.com0tag:blogger.com,1999:blog-4949960181628888221.post-43303147591649025532010-03-13T12:48:00.005+08:002010-03-13T12:58:57.780+08:00【筆記】Create a Verilog Project 安裝好 Verilog 的撰寫環境--Quartus II 之後,我們還需要建置好一個專案(project)才能正式開始。所以,這裡簡單的描述一下建立專案,以及編譯 Verilog 原始碼的流程。<br />
<span id="detail">
<br />
<br />
<br />
首先,點選選單的 <b>File/New Project Wizard</b>。就會跳出一個專案的建置精靈:<br />
<br />
<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://4.bp.blogspot.com/_1111KAvK4Ds/S5sX_HxKXcI/AAAAAAAABM4/TxVbPMSFZ1M/s1600-h/verilog(3).ex1.JPG"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 520px;" src="http://4.bp.blogspot.com/_1111KAvK4Ds/S5sX_HxKXcI/AAAAAAAABM4/TxVbPMSFZ1M/s800/verilog(3).ex1.JPG" border="0" alt=""id="BLOGGER_PHOTO_ID_5447974547419192770" /></a><br />
<br />
在「<b>What is the working directory for this project?</b>」中輸入你專案的擺放路徑,並在「<b>What is the name of this project?</b>」中輸入專案的名稱(註1)。<br />
<br />
若是專案路徑的資料夾不存在,會跳出訊息問你是否要建立它:<br />
<br />
<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://4.bp.blogspot.com/_1111KAvK4Ds/S5sX_U5hR_I/AAAAAAAABNA/yNOlrCCyc3I/s1600-h/verilog(3).ex2.JPG"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;" src="http://4.bp.blogspot.com/_1111KAvK4Ds/S5sX_U5hR_I/AAAAAAAABNA/yNOlrCCyc3I/s800/verilog(3).ex2.JPG" border="0" alt=""id="BLOGGER_PHOTO_ID_5447974550943909874" /></a><br />
<br />
確定要建立,就選擇「是」。<br />
<br />
<br />
<br />
按下 Next 之後,我們可以加入一些現有的檔案到專案裡頭:<br />
<br />
<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://1.bp.blogspot.com/_1111KAvK4Ds/S5sX_kFh8gI/AAAAAAAABNI/E32480aI0gg/s1600-h/verilog(3).ex3.JPG"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 520px;" src="http://1.bp.blogspot.com/_1111KAvK4Ds/S5sX_kFh8gI/AAAAAAAABNI/E32480aI0gg/s800/verilog(3).ex3.JPG" border="0" alt=""id="BLOGGER_PHOTO_ID_5447974555020816898" /></a><br />
<br />
你可以利用 File name 後方的「...」按鈕開啟檔案對話方塊,選擇要加入的檔案,再按下 Add 按鈕加入專案。也可以直接按下 Add All 將目錄下的檔案都加到專案中。<br />
<br />
不過,這裡我們還沒有任何現存的檔案可以加入,所以直接按下 Finish 完成專案建置(註2)。<br />
<br />
<br />
<br />
建立好專案之後,我們還需要建立一個 Verilog 的原始碼檔案。按下選單的 <b>File/New</b>,就會出現對話框詢問你新增的檔案類型:<br />
<br />
<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://3.bp.blogspot.com/_1111KAvK4Ds/S5sYANahXdI/AAAAAAAABNQ/C-9VUn1eeyU/s1600-h/verilog(3).ex4.JPG"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand; width:362px;" src="http://3.bp.blogspot.com/_1111KAvK4Ds/S5sYANahXdI/AAAAAAAABNQ/C-9VUn1eeyU/s800/verilog(3).ex4.JPG" border="0" alt=""id="BLOGGER_PHOTO_ID_5447974566114713042" /></a><br />
<br />
由於我們要是 Verilog 的原始碼檔案,所以選擇「<b>Verilog HDL File</b>」。<br />
<br />
新增完成之後,就可以直接開始撰寫程式碼(下圖中的程式碼為先前 <a href="http://program-lover.blogspot.com/2010/03/verilog-module.html">Verilog Module</a> 解釋的 AndGate Module):<br />
<br />
<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://4.bp.blogspot.com/_1111KAvK4Ds/S5sYATGFvwI/AAAAAAAABNY/pr379zdC6K8/s1600-h/verilog(3).ex5.JPG"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 520px;" src="http://4.bp.blogspot.com/_1111KAvK4Ds/S5sYATGFvwI/AAAAAAAABNY/pr379zdC6K8/s800/verilog(3).ex5.JPG" border="0" alt=""id="BLOGGER_PHOTO_ID_5447974567639629570" /></a><br />
<br />
接下來將檔案存檔:<br />
<br />
<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://2.bp.blogspot.com/_1111KAvK4Ds/S5sYXVsv-bI/AAAAAAAABNg/c6-OdpWoWxk/s1600-h/verilog(3).ex6.JPG"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 520px;" src="http://2.bp.blogspot.com/_1111KAvK4Ds/S5sYXVsv-bI/AAAAAAAABNg/c6-OdpWoWxk/s800/verilog(3).ex6.JPG" border="0" alt=""id="BLOGGER_PHOTO_ID_5447974963475642802" /></a><br />
<br />
請記得,<font color="red"><b>Quartus II 的主要模組一定要跟檔案名稱相同</b></font>。<br />
<br />
<br />
<br />
接下來,就可以按下選單的 Precessing/Start Compilation 開始編譯的動作。假如跳出「Full Compilation was successful」的對話框,就代表編譯成功了(註3):<br />
<br />
<a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://1.bp.blogspot.com/_1111KAvK4Ds/S5sYXlaxriI/AAAAAAAABNo/f--8xRLBoz0/s1600-h/verilog(3).ex7.JPG"><img style="display:block; margin:0px auto 10px; text-align:center;cursor:pointer; cursor:hand;width: 287px; height: 123px;" src="http://1.bp.blogspot.com/_1111KAvK4Ds/S5sYXlaxriI/AAAAAAAABNo/f--8xRLBoz0/s800/verilog(3).ex7.JPG" border="0" alt=""id="BLOGGER_PHOTO_ID_5447974967695224354" /></a><br />
<br />
<br />
<blockquote>
註1. 建議將專案放在獨立的地方,並為專案取個有意義的名稱,方便以後重複使用專案。<br />
註2. 實際上後面還有一些設定燒錄晶片跟相關工具的部份,不過這裡我們目前都用不到。<br />
註3. 這裡會看到其實編譯過程中會有些警告訊息。雖然這裡我們並不在意它,不過你也可以去看看這些警告訊息,查查到底為什麼。
</blockquote>
</span>Anonymoushttp://www.blogger.com/profile/17636157464310241832noreply@blogger.com0tag:blogger.com,1999:blog-4949960181628888221.post-84599720363968998372010-03-13T00:09:00.004+08:002010-03-13T00:18:30.325+08:00【筆記】Verilog Module 在之前的<a href="http://program-lover.blogspot.com/2010/03/verilog-0.html">簡介</a>中提到,Verilog 以<b>模組(module)</b>作為描述的基本單位。模組如同程式語言中的函式(function),可以將一部份的程式碼封裝起來,並提供對外溝通的介面(interface)。如此一來,我們便可以重複利用這些定義好的模組,以構成較大、較複雜的系統。<br />
<span id="detail">
<br />
<br />
<br />
我們可以將模組看成兩個部份:<b>連接埠(port)的宣告</b>,以及<b>模組的主體(body)</b>。<br />
<br />
其中,連接埠類似於程式語言中函式的參數(parameter),<u>提供了對外溝通的介面</u>。包含了<b>輸入埠(input)</b>、<b>輸出埠(output)</b>、或是兼具輸出入的<b>雙向埠(inout)</b>。簡單來說的話,其實可以把連接埠想成一顆 IC 上面的接腳(pin)。<br />
<br />
而模組主體則類似於程式語言中的函式主體,<u>表達了模組的結構,或是模組的功能與行為</u>。<br />
<br />
<br />
<br />
以下是一個 Verilog 的模組,代表一個 and 邏輯閘:<br />
<br />
<pre class="code">
module AndGate(out, a, b);
input a, b;
output out;
and(out, a, b);
endmodule
</pre>
<br />
接著,讓我們一步一步理解這個簡易的模組。<br />
<br />
<br />
<br />
<pre class="code">
module AndGate(out, a, b);
</pre>
<br />
這裡的「<b>module</b>」為 Verilog 語法的關鍵字,代表一個模組宣告的開頭;「AndGate」為這個模組的名稱(註1);而括號中的 out、a、跟 b,則是這個模組的連接埠(註2)。<br />
<br />
不過,在這裡並沒有指明連接埠的類型(input、output、或是 inout)。所以我們將在下面兩行宣告它們:<br />
<br />
<pre class="code">
input a, b;
output out;
</pre>
<br />
我們宣告 a 跟 b 為 AndGate 的輸入埠,且 out 為 AndGate 的輸出埠。<br />
<br />
<br />
<br />
而模組主體的部份,我們只做了一個簡單的動作:<br />
<br />
<pre class="code">
and(out, a, b);
</pre>
<br />
「and」為 Verilog 提供的內建邏輯閘。這裡的動作是將輸入埠 a 跟 b 進行 and 運算,並以輸出埠 out 作為運算後的結果(註3)。<br />
<br />
<br />
<br />
最後,我們以「<b>endmodule</b>」關鍵字結束模組的宣告:<br />
<br />
<pre class="code">
endmodule
</pre>
<br />
<br />
<br />
這個模組的示意圖大致如下:<br />
<br />
<center><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://3.bp.blogspot.com/_1111KAvK4Ds/S5pnTfIZH2I/AAAAAAAABMw/89xcQhldCyM/s1600-h/verilog(2).ex1.JPG"><img style="cursor:pointer; cursor:hand;width: 216px; height: 136px;" src="http://3.bp.blogspot.com/_1111KAvK4Ds/S5pnTfIZH2I/AAAAAAAABMw/89xcQhldCyM/s800/verilog(2).ex1.JPG" border="0" alt=""id="BLOGGER_PHOTO_ID_5447780283729911650" /></a></center><br />
<br />
<br />
<blockquote>
註1. 你可以根據模組的功能,自行取一個有意義的名稱。<br />
註2. 一般來說,我們習慣將 output 寫在前面、將 input 寫在後面。<br />
註3. 或許想成「將 a 跟 b 接到 and gate 的 input 接腳,並將 out 接到 and gate 的 output 接腳」會比較好理解。
</blockquote>
</span>Anonymoushttp://www.blogger.com/profile/17636157464310241832noreply@blogger.com0tag:blogger.com,1999:blog-4949960181628888221.post-45846147952883154782010-03-12T19:34:00.007+08:002010-03-12T21:14:16.742+08:00【筆記】Quartus II Installation 在實際開始撰寫 Verilog 之前,我們需要先安裝好撰寫執行 Verilog 程式的環境工具。而這裡我們採用的工具,是 <a href="http://www.altera.com/">Altera</a> 公司的 Quartus II 這套軟體。<br />
<br />
<span id="detail">
Quartus II 是一套用以撰寫 Verilog、VHDL、AHDL 等 HDL 的開發工具,除了可以進行程式的編輯與編譯之外,也可以用以產生邏輯圖、狀態圖、波形圖等等,在功能上算是相當齊全。<br />
<br />
<br />
<br />
現行的 Quartus II 有兩個不同的版本:Web Edition 與 Subscription Edition。<br />
<br />
其中 Subscription Edition 有提供 30 天的試用期。超過試用期之後,是需要經過授權才可以繼續使用的。而 Web Edition 則是免費的版本,可以直接下載來使用。<br />
<br />
這裡我們要使用的是 <a href="http://www.altera.com/products/software/quartus-ii/web-edition/qts-we-index.html"><b>Web Edition</b></a>。<br />
<br />
<br />
<br />
要取得 Quartus II Web Edition,需要先連到其<a href="https://www.altera.com/support/software/download/altera_design/quartus_we/dnl-quartus_we.jsp">下載頁面</a>:<br />
<br />
<center><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://4.bp.blogspot.com/_1111KAvK4Ds/S5ol6Dhbt5I/AAAAAAAABMI/3mYQzJJ9Z2c/s1600-h/verilog(1).ex1.JPG"><img style="cursor:pointer; cursor:hand;width: 520px;" src="http://4.bp.blogspot.com/_1111KAvK4Ds/S5ol6Dhbt5I/AAAAAAAABMI/3mYQzJJ9Z2c/s800/verilog(1).ex1.JPG" border="0" alt=""id="BLOGGER_PHOTO_ID_5447708378566211474" /></a></center><br />
<br />
然後,選擇下載「<b>Quartus® II Web Edition Software v9.1 Service Pack 1</b>」(請依照當前最新版本自行尋找)。<br />
<br />
<center><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://3.bp.blogspot.com/_1111KAvK4Ds/S5ol6gF0LUI/AAAAAAAABMQ/FgSiOQi-0bY/s1600-h/verilog(1).ex2.JPG"><img style="cursor:pointer; cursor:hand;width: 520px;" src="http://3.bp.blogspot.com/_1111KAvK4Ds/S5ol6gF0LUI/AAAAAAAABMQ/FgSiOQi-0bY/s800/verilog(1).ex2.JPG" border="0" alt=""id="BLOGGER_PHOTO_ID_5447708386235002178" /></a></center><br />
<br />
接著會進到 Account Sign-In 的畫面。假設各位都沒有 Altera 的帳號,可以選擇「<b>Get One-Time Access</b>」並在下面的文字框輸入你的 E-mail,就能夠不經由註冊的步驟繼續下載。<br />
<br />
當然,若是你真的想註冊一個帳號,選擇「Create Your myAltera Account」並完成註冊步驟也是可以的。<br />
<br />
<center><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://3.bp.blogspot.com/_1111KAvK4Ds/S5ol6423cuI/AAAAAAAABMY/jplDq5DToDs/s1600-h/verilog(1).ex3.JPG"><img style="cursor:pointer; cursor:hand;width: 520px;" src="http://3.bp.blogspot.com/_1111KAvK4Ds/S5ol6423cuI/AAAAAAAABMY/jplDq5DToDs/s800/verilog(1).ex3.JPG" border="0" alt=""id="BLOGGER_PHOTO_ID_5447708392883188450" /></a></center><br />
<br />
最後,拉到頁面下方,點選「<b>Click to Download Your File Now</b>」,就可以進行下載,並開始安裝(因為安裝過程只需要選擇安裝路徑,這裡就不花版面贅述了)。<br />
<br />
由於檔案大小高達 1.5GB,下載跟安裝的動作比較耗時,所以可能需要耐心等待一下子。<br />
<br />
<br />
<br />
安裝完成之後,就可以開始使用 Quartus II 這套功能強大的工具囉:<br />
<br />
<center><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://3.bp.blogspot.com/_1111KAvK4Ds/S5onzPmipYI/AAAAAAAABMg/zOB1ql4mmJ4/s1600-h/verilog(1).ex4.JPG"><img style="cursor:pointer; cursor:hand;width: 520px;" src="http://3.bp.blogspot.com/_1111KAvK4Ds/S5onzPmipYI/AAAAAAAABMg/zOB1ql4mmJ4/s800/verilog(1).ex4.JPG" border="0" alt=""id="BLOGGER_PHOTO_ID_5447710460573033858" /></a></center>
</span>Anonymoushttp://www.blogger.com/profile/17636157464310241832noreply@blogger.com3tag:blogger.com,1999:blog-4949960181628888221.post-18044950301239723692010-03-12T19:31:00.004+08:002010-03-12T21:03:45.193+08:00【筆記】Introduction to Verilog 因為系上這學期有一門要寫 Verilog 的必修課,所以想說乾脆直接在 blog 上做個筆記整理內容,並供一起上課的同學們作為參考。不過,其中的許多內容都不是我非常瞭解的,假如有任何錯誤或問題,都歡迎各位提出來。<br />
<span id="detail">
<br />
<br />
<br />
說到 <a href="http://en.wikipedia.org/wiki/Verilog"><b>Verilog</b></a> 就不能不先提到 <a href="http://en.wikipedia.org/wiki/Hardware_description_language"><b>HDL(Hardware Description Language,硬體描述語言)</b></a>。<br />
<br />
所謂 HDL,即是利用一般高階語言的程式撰寫法,以達成數位電路功能或結構的設計、驗證與模擬。利用 HDL,我們便可以不必透過傳統的手繪方式設計電路,再在麵包板上接出電路來進行驗證與模擬。而 Verilog 則是主流的兩種 HDL 之一(註1)。<br />
<br />
Verilog 在設計時採用了近似於 C 語言的語法,以類似於函式(function)的<b>模組(module)</b>作為描述的基本單位。對於熟悉 C 語言的程式設計師來說,Verilog 還算是相當容易學習。<br />
<br />
<br />
<br />
在實際的設計上,Verilog 則提供了四種層級的描述方式,供設計者在不同層次的觀點上設計電路。分別為:<b>開關層級(Switch Level)</b>、<b>邏輯閘層級(Gate Level)</b>、<b>資料流層級(Dataflow Level)</b>與<b>行為層級(Behavioral Level)</b>。<br />
<br />
開關層級是 Verilog 所提供的最低層級。在這個層級上,設計者需要瞭解電路的開關--電晶體(transistor)的元件特性,並以此進行電路的設計。<br />
<br />
在邏輯閘層級中,設計者的觀點從一個個的電晶體,轉到較高層的邏輯閘(logic gate)。以此觀點,設計者可以直接利用如 and、or、not、xor 等邏輯閘,與將之連接的線路來進行設計。<br />
<br />
在資料流層級中,我們關注的則是資料如何經由硬體元件進行處理、儲存、與流向;而在最高層級的行為層級上,設計者只需要知道模組與函式間的功能,而不去考慮硬體實作的細節。<br />
<br />
<center><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://4.bp.blogspot.com/_1111KAvK4Ds/S5ooCyAABWI/AAAAAAAABMo/PYj_luxNDVk/s1600-h/verilog(0).ex1.png"><img style="cursor:pointer; cursor:hand;width: 350px; height: 230px;" src="http://4.bp.blogspot.com/_1111KAvK4Ds/S5ooCyAABWI/AAAAAAAABMo/PYj_luxNDVk/s800/verilog(0).ex1.png" border="0" alt=""id="BLOGGER_PHOTO_ID_5447710727504659810" /></a></center><br />
<br />
<br />
<blockquote>
註1. 另一種常用的硬體描述語言是 <a href="http://en.wikipedia.org/wiki/VHDL">VHDL(Very-High-Speed Integrated Circuit Hardware Description Language)</a>。
</blockquote>
</span>Anonymoushttp://www.blogger.com/profile/17636157464310241832noreply@blogger.com2tag:blogger.com,1999:blog-4949960181628888221.post-30447571489713007542010-03-07T13:09:00.005+08:002010-03-20T19:14:23.349+08:00【演算】氣泡排序法 - Bubble Sort <a href="http://en.wikipedia.org/wiki/Bubble_sort"><b>氣泡排序法(bubble sort)</b></a>是<a href="http://en.wikipedia.org/wiki/Sorting_algorithm">排序演算法(sorting algorithm)</a>中較簡易的一種。其運作的原理是藉由逐次比較相鄰的兩筆資料,並依照排序條件(由大至小或由小至大)交換資料直到排序完成為止。<br />
<span id="detail">
<br />
<br />
<br />
假設現在我們需要將 n 筆資料 A<sub>1</sub>、A<sub>2</sub>、......、A<sub>n</sub> 由小排到大。<br />
<br />
一開始,我們需要先比較 A<sub>1</sub> 與 A<sub>2</sub> 兩筆資料的大小。若是 A<sub>1</sub> > A<sub>2</sub>,則交換兩筆資料;接著比較 A<sub>2</sub> 與 A<sub>3</sub>。若是 A<sub>2</sub> > A<sub>3</sub>,則交換兩筆資料;以此類推,一直到比較完 A<sub>n - 1</sub> 與 A<sub>n</sub> 為止。<br />
<br />
<br />
<br />
這樣就完了嗎?當然還沒。到目前為止,我們只確定 A<sub>n</sub> 是 n 筆資料中最大的數字。<br />
<br />
接下來,重複剛剛的動作:比較 A<sub>1</sub> 與 A<sub>2</sub>、A<sub>2</sub> 與 A<sub>3</sub>、A<sub>3</sub> 與 A<sub>4</sub>、......,不同的是,這一次只需要比較到 A<sub>n - 2</sub> 與 A<sub>n - 1</sub> 即可。到目前為止,我們可以確定 A<sub>n - 1</sub> 是 n 筆資料中次大的數字。<br />
<br />
接著就繼續重複同樣的動作,便能確定每一輪比較中的最大資料,皆在這些資料的最後面。直到所有資料排序完成為止。<br />
<br />
<br />
<br />
其原理的虛擬碼大致如下:<br />
<br />
<pre class="code">
Function bubbleSort(Type data[1..n])
Index i, j;
For i from n to 2 do
For j from 1 to i - 1 do
If data[j] > data[j + 1] then
Exchange data[j] and data[j + 1]
End
</pre>
<br />
<br />
<br />
讓我們舉個實際的例子來說明。若是我們現在要將以下這些資料由大排到小:<br />
<br />
<blockquote>
1 43 6 79 50 2
</blockquote>
<br />
則第一輪的比較與交換過程如下:<br />
<br />
<blockquote>
<font color="red"><b>43 1</b></font> 6 79 50 2
</blockquote>
<blockquote>
43 <font color="red"><b>6 1</b></font> 79 50 2
</blockquote>
<blockquote>
43 6 <font color="red"><b>79 1</b></font> 50 2
</blockquote>
<blockquote>
43 6 79 <font color="red"><b>50 1</b></font> 2
</blockquote>
<blockquote>
43 6 79 50 <font color="red"><b>2 1</b></font>
</blockquote>
<br />
第二輪的比較與交換過程如下:<br />
<br />
<blockquote>
<font color="green"><b>43 6</b></font> 79 50 2 1
</blockquote>
<blockquote>
43 <font color="red"><b>79 6</b></font> 50 2 1
</blockquote>
<blockquote>
43 79 <font color="red"><b>50 6</b></font> 2 1
</blockquote>
<blockquote>
43 79 50 <font color="green"><b>6 2</b></font> 1
</blockquote>
<br />
接下來以此類推。<br />
<br />
由此可以看到,資料中較小的一筆會藉由交換慢慢「浮」到資料頂端,其「氣泡排序」之名也是因此而來。<br />
<br />
<br />
<br />
若是我們分析在最差情況下(即所有資料的順序剛好完全相反,因為我們必須在每一輪迴圈,藉由不斷交換兩筆資料的動作,把最前頭的資料移到最後面),使用氣泡排序法將 n 筆資料排序的敘述執行次數(註1):<br />
<br />
<pre class="code">
Function bubbleSort(Type data[1..n])
Index i, j; // 1
For i from n to 2 do // n - 1
For j from 1 to i - 1 do // n(n - 1) / 2
If data[j] > data[j + 1] then // n(n - 1) / 2
Exchange data[j] and data[j + 1] // n(n - 1) / 2
End
</pre>
<br />
可得出所有敘述的執行次數總和為:W(n) = 1 + (n - 1) + n(n - 1) / 2 + n(n - 1) / 2 + n(n - 1) / 2 = (3n<sup>2</sup> - n) / 2 ∈ Ο(n<sup>2</sup>),為一個平方時間(quadratic time)的演算法。<br />
<br />
<br />
<br />
而在最好的情況下(即所有資料都為已排序狀態,因為不需要進行任何一次交換動作):<br />
<br />
<pre class="code">
Function bubbleSort(Type data[1..n])
Index i, j; // 1
For i from n to 2 do // n - 1
For j from 1 to i - 1 do // n(n - 1) / 2
If data[j] > data[j + 1] then // n(n - 1) / 2
Exchange data[j] and data[j + 1] // 0
End
</pre>
<br />
所有敘述的執行次數總和為:B(n) = 1 + (n - 1) + n(n - 1) / 2 + n(n - 1) / 2 + 0 = n<sup>2</sup> ∈ Ο(n<sup>2</sup>)。複雜度依舊為平方時間。<br />
<br />
對於一種排序演算法而言,這樣複雜度是相當沒有效率的。因此這個方法多半只是被拿來簡單的解釋排序概念,而不是拿來實際應用。<br />
<br />
<br />
<blockquote>
註1. 其中的 n(n - 1) / 2 是由 (n - 1) + (n - 2) + (n - 3) + ... + 1 加總化簡而來。
</blockquote>
</span>Anonymoushttp://www.blogger.com/profile/17636157464310241832noreply@blogger.com3tag:blogger.com,1999:blog-4949960181628888221.post-72336282967549228132010-03-07T00:02:00.004+08:002010-03-07T00:23:38.629+08:00【演算】遞迴函式 - Recursive Function 所謂的<a href="http://en.wikipedia.org/wiki/Recursion_(computer_science)"><b>遞迴(recursion)</b></a>,簡單來說就是「<a href="http://en.wikipedia.org/wiki/Subroutine">函式(function)</a>不斷呼叫自身」的一種程式撰寫法。遞迴的意義,在於把一個問題切割成相同性質的較小問題來解決。而為了防止程式無窮盡的遞迴下去,我們還必須為所寫出來的遞迴函式設定一個<b>終止條件(termination condition)</b>。<br />
<span id="detail">
<br />
遞迴的原理,是利用函式本身的<a href="http://en.wikipedia.org/wiki/Call_stack"><b>堆疊(stack)</b></a>性質--<a href="http://en.wikipedia.org/wiki/LIFO"><b>後進先出(last in, first out,LIFO)</b></a>來達成的。說得簡單一點,就是當某個函式呼叫另一個函式時,其會先執行完被呼叫的函式,才繼續執行自身的函式內容。<br />
<br />
<br />
<br />
讓我們舉一個常見的例子來解釋:<a href="http://en.wikipedia.org/wiki/Factorial">階乘(factorial)</a>。<br />
<br />
在數學上的定義中,對於一個非負整數 n,其階乘代表的是所有小於或等於 n 的正整數乘積,記作 n!。即 n! = 1 × 2 × 3 × ... × n。若我們規定 0! = 1,則可以將之改寫成:對於所有非負整數 n,(n + 1)! = (n + 1) × n!。<br />
<br />
於是,我們便可以利用程式寫出計算階乘的遞迴函式。以下為其虛擬碼:<br />
<br />
<pre class="code">
Function factorial(Integer n)
If n = 0 then
Return 1
Else
Return n × factorial(n - 1)
End
</pre>
<br />
在這裡,我們相當於將原始的問題 n! 看作是 n × (n - 1)! 這個較小的問題。也就是得知 (n - 1)! 的值,就可以求得 n! 的解。同樣的,又可以將 (n - 1)! 看作是 (n - 1) × (n - 2)!、將 (n - 2)! 看作是 (n - 2) × (n - 3)!、......。<br />
<br />
舉例來說,若是我們需要利用程式求出 6! 的值。則在我們呼叫 factorial(6) 時,為了得出結果,亦須求出 factorial(5) 的值。而為了得出 factorial(5) 的結果,我們亦須求出 factorial(4) 的值......。一直不斷遞迴下去,直到達到終止條件:n = 0 為止。<br />
<br />
實際運作的結果,就如下圖所示意的(藍箭頭代表呼叫,紅箭頭代表回傳):<br />
<br />
<center><a onblur="try {parent.deselectBloggerImageGracefully();} catch(e) {}" href="http://4.bp.blogspot.com/_1111KAvK4Ds/S5J8KeQ6QlI/AAAAAAAABLw/r6gMX9ZobeI/s1600-h/recursion.ex1.png"><img style="cursor:pointer; cursor:hand;width: 520px;" src="http://4.bp.blogspot.com/_1111KAvK4Ds/S5J8KeQ6QlI/AAAAAAAABLw/r6gMX9ZobeI/s800/recursion.ex1.png" border="0" alt=""id="BLOGGER_PHOTO_ID_5445551418808877650" /></a></center><br />
<br />
<br />
<br />
除此之外,遞迴還可以解決相當多其他的問題。例如<a href="http://program-lover.blogspot.com/2008/08/fibonacci-sequence.html">斐波那契數列(fibonacci sequence)</a>、<a href="http://program-lover.blogspot.com/2008/05/mouse-in-maze.html">老鼠走迷宮(mouse in a maze)</a>、以及<a href="http://program-lover.blogspot.com/2008/06/tower-of-hanoi.html">河內塔(tower of hanoi)</a>等等,這裡我就不加贅述了。<br />
<br />
<br />
<br />
雖然利用程式的遞迴解法較為直觀,但是不斷堆疊函式的結果,極有可能浪費了過多的記憶體空間。其實,遞迴的程式多半都能藉由迴圈的方式替代,只是程式也可能會因此變得複雜難懂。至於實際上要使用何者,就看你怎麼選擇囉。
</span>Anonymoushttp://www.blogger.com/profile/17636157464310241832noreply@blogger.com7tag:blogger.com,1999:blog-4949960181628888221.post-46572154876443559192010-03-06T21:34:00.006+08:002010-03-06T21:59:08.795+08:00【演算】複雜度分析 - Complexity Analysis 在<a href="http://program-lover.blogspot.com/2008/08/algorithm.html">演算法簡介</a>中,我們提到了「找電話」問題的兩個演算法:分別為「依序找」跟「按筆劃找」。我們可以知道,對於相同的問題,可能會同時存在許多不同的解法。然而在這種擁有多種可能解法的情況下,我們理應對這些演算法進行評估,並從中選擇一種最有效的方式。<br />
<span id="detail">
<br />
<br />
<br />
從比較執行時間的層面來看,或許你會想到:直接利用計時器來比較不同演算法實現程式的執行時間。但是,這種方式的變因太多。實作演算法的程式語言、記憶體大小、不同的編譯(直譯)器、甚至是電腦中運行的程式,可能都會影響計時所得的結果。相對的,這種方式也就顯得不太準確。<br />
<br />
除了實際去計時之外,我們也可以假設演算法中「每一步」的執行時間都相同。於是,我們也可以直接拿演算法所有「步驟」的執行次數總和來進行比較。<br />
<br />
<br />
<br />
讓我們同樣以「依序找電話」演算法為例。<br />
<br />
先考慮在最差情況(worst case)下(也就是欲尋找的電話號碼不在電話簿中,因為你必須搜遍整本電話簿),「依序找電話」虛擬碼每行敘述的執行次數如下(方便起見,我們以變數 n 代表電話簿的大小 phoneBook.size):<br />
<br />
<pre class="code">
Input name // 1
While True do // n
If index > phoneBook.size then // n
Output "phone number not found" // 1
Break loop // 1
If phoneBook.record[index].name = name then // n
Output phoneBook.record[index].phone // 0
Break loop // 0
index = index + 1 // n
</pre>
<br />
因此在最差情況下,每行敘述的執行次數總和:<b>W(n) = 1 + n + n + 1 + 1 + n + 0 + 0 + n = 4n + 3</b>。<br />
<br />
由此可以發現,<u>一個演算法的執行時間通常會隨著輸入資料的大小 n 的成長而成長</u>(註1)。而這個與資料大小 n 相關的時間(或空間)函數,則稱為這個演算法的<b>複雜度(complexity)</b>。<br />
<br />
<br />
<br />
不過,我們還可以用更簡明、更具數學意義的方式來表達它。<br />
<br />
首先,我們可以知道當 n 是一個相當大的數字時,4n 是遠大於 3 的。換句話說,就是我們只需要保留函數的最高項,也就是這個例子中的 4n。而若是只想考慮其函數的成長趨勢,我們甚至可以連其係數一併省略,只注意 n 這個部份,代表這個演算法是一個線性時間(linear time)的演算法,記作 O(n)。<br />
<br />
<br />
<br />
<a href="http://en.wikipedia.org/wiki/Big_O_notation"><b>Ο(big-omicron,或是稱作 big-O)</b></a>是一個<b>漸進符號(asymptotic notation)</b>,代表了函數的<b>漸進上限(asymptotic upper bound)</b>。其定義如下:<br />
<br />
<blockquote>
對於兩個非負函數 f(n) 與 g(n),若且唯若存在一正整數 n<sub>0</sub> 與 c > 0,使得所有整數 n ≥ n<sub>0</sub> 都滿足 0 ≤ f(n) ≤ cg(n),則 f(n) ∈ Ο(g(n))。
</blockquote>
<br />
簡單來說,若是我們說一個演算法的複雜度函數 f(n) ∈ Ο(g(n)),就代表函數 f(n) 的成長趨勢與 g(n) 相似或是更慢的。<br />
<br />
<br />
<br />
除了 big-omicron 之外,我們還可以使用 <b>Ω(big-omega)</b>、<b>Θ(big-theta)</b>、<b>ο(little-omicron)</b>與 <b>ω(little-omega)</b>來表達一個演算法的複雜度。<br />
<br />
big-omega 代表了函數的<b>漸進下限(asymptotic lower bound)</b>。簡單來說,若是我們說一個演算法的複雜度函數 f(n) ∈ Ω(g(n)),就代表 f(n) 函數圖形的成長趨勢與 g(n) 相似或是更快的。其正式的定義如下:<br />
<br />
<blockquote>
對於兩個非負函數 f(n) 與 g(n),若且唯若存在一正整數 n<sub>0</sub> 與 c > 0,使得所有整數 n ≥ n<sub>0</sub> 都滿足 0 ≤ cg(n) ≤ f(n),則 f(n) ∈ Ω(g(n))。
</blockquote>
<br />
<br />
<br />
那麼 big-theta 呢?其實,big-theta 也就相等於 big-omicron 與 big-omega 的交集,也就是 Θ(g(n)) = Ο(g(n)) ∩ Ω(g(n)),代表 f(n) 函數圖形的成長趨勢與 g(n) 是相似的。其正式的定義如下:<br />
<br />
<blockquote>
對於兩個非負函數 f(n) 與 g(n),若且唯若存在一正整數 n<sub>0</sub>, c<sub>1</sub>與 c<sub>2</sub> > 0,使得所有整數 n ≥ n<sub>0</sub> 都滿足 c<sub>1</sub>g(n) ≤ f(n) ≤ c<sub>2</sub>g(n),則 f(n) ∈ Θ(g(n))。
</blockquote>
<br />
<br />
<br />
而 little-omicron 與 little-omega 則分別為 big-omicron 與 big-omega 和 big-theta 的差集,即 ο(g(n)) = Ο(g(n)) - Θ(g(n)), ω(g(n)) = Ω(g(n)) - Θ(g(n))。以下為其正式定義:<br />
<br />
<blockquote>
對於兩個非負函數 f(n) 與 g(n),若且唯若存在一正整數 n<sub>0</sub> 與 c > 0,使得所有整數 n ≥ n<sub>0</sub> 都滿足 0 ≤ f(n) < cg(n),則 f(n) ∈ ο(g(n))。
</blockquote>
<br />
<blockquote>
對於兩個非負函數 f(n) 與 g(n),若且唯若存在一正整數 n<sub>0</sub> 與 c > 0,使得所有整數 n ≥ n<sub>0</sub> 都滿足 0 ≤ cg(n) < f(n),則 f(n) ∈ ω(g(n))。
</blockquote>
<br />
<br />
<br />
為了方便比較,我們可以將 f(n) 與 g(n) 比擬成 a 跟 b,則:<br />
<ul>
<li>f(n) ∈ Ο(g(n)) ≈ a ≤ b</li>
<li>f(n) ∈ Ω(g(n)) ≈ a ≥ b</li>
<li>f(n) ∈ Θ(g(n)) ≈ a = b</li>
<li>f(n) ∈ ο(g(n)) ≈ a < b</li>
<li>f(n) ∈ ω(g(n)) ≈ a > b</li>
</ul>
<br />
<br />
雖然存在這麼多種漸進符號以表達演算法的複雜度,但是一般來說,當我們分析一個演算法的複雜度,比較常使用 big-omicron 來表達估算後的結果。這是因為對於一個演算法,其所耗費的時間(或是記憶體)上限,通常才是我們需要關注的重點。<br />
<br />
<br />
<blockquote>
註1. 對於演算法所使用的記憶體空間,通常也是如此。
</blockquote>
</span>Anonymoushttp://www.blogger.com/profile/17636157464310241832noreply@blogger.com3