Tag Archive 'Algorithm'

以目前全球資訊網上擁有的巨量資訊,如果沒有高效率搜尋引擎的幫助,尋找資訊將如同大海撈針一般困難,今天已有許多商業的搜尋引擎試圖滿足此類搜尋工作的需求,例如:Google,Yahoo,Ask與Microsoft Live Search等。搜尋引擎多會依照某種方式進行排序,把相關的網路搜尋結果以排名順序列表一一提供使用者去瀏覽,讓使用者依照搜尋結果摘要的內容自行挑選。然而這樣的瀏覽方式極度沒有效率,因為網路搜尋結果通常相當的多,而一般使用者多只會有耐心瀏覽前若干筆的搜尋結果,而且這類排名順序列表的呈現方式會使得很多關於使用者查詢的子議題通通混雜在一起,很容易造成使用者錯過重要資訊。

Read Full Post »

Posted By Mr. Thursday 不知道各位是否有接聽電話插撥 (call waiting) 的經驗? 我們會先把第一個接聽的人先暫時停著,然後接聽新打來的電話。不知道目前插撥最多能接聽多少通電話?假設依照這個方法一直接聽新的插撥電話,就會一直把上一通電話暫時儲存,等新接通的電話結束後,再回復上一通、上上一通、一直到第一通接聽的電話。 堆疊 (Stack) 就是類似的資料結構。「堆疊」有兩個方法 (method) 可以呼叫:推進 (push) 和 彈出 (pop)。透過這兩個方法的使用,我們可以達到讓資料「先進後出」的效果 (LIFO: Last In First Out)。甚麼是先進後出呢?讓我們再舉一個例子:搭電梯。當我們搭電梯的時候,通常最先進電梯的會擠在後面,後進電梯的比較靠近門口。如果都是同一層離開電梯,剛才比較慢近來電梯的人,反而是比較早離開電梯的人,這就是「先進後出」(LIFO) 的效果了。 再回到剛才接聽插撥電話的例子,正好就是先進後出的例子!最後插撥的先結束對話,最早打來的最慢結束對話。接下來讓我們看看,堆疊實際運作的情形,會向下面這一張動畫所顯示的:  

Read Full Post »

Posted By Mr. Thursday 在〈由樹的前序、中序、後序走法來談資料結構〉文章裡面提到了演算法就像是做事情的方法,資料結構則是對應演算法可以運作的東西,譬如說刮鬍子有步驟一、步驟二、步驟三,但是要有刮鬍刀、插頭、以及鬍鬚,那些步驟才有運作的東西,甚至不同的刮鬍刀,也會讓同樣的步驟有不同的執行效率,或是連原來的步驟都要改變,譬如說不是電動刮鬍刀,原來步驟裡面插插頭的那一步,也就可以不用作了。演算法和資料結構之間的關係也是如此,譬如說排序的演算法,可以用不同的資料結構來實現,好的資料結構,可能某一種排序演算法最適合,對其他種排序演算法,可能反而讓速度變慢。 因此,演算法和資料結構,通常會一起考慮,而演算法每一步,也就是電腦可以實現的基本步驟所組成。譬如說兩個數字相加,或是把「樹」這個資料結構裡面的節點根據某種規則移動,都是電腦運算基本步驟所可以達成的。但是如果步驟是「改善排序的品質」的敘述,電腦可能就看不懂了,這時候就是程式設計師,把這些人看的懂的需求,轉換成電腦可以實現的步驟,也就是演算法和對應的資料結構,最後再用程式 (編程) (program),變成電腦真的可以執行的語言,達到最初想要執行的功能。那麼今天想要完成的功能是甚麼呢?「排序」,排序就是把原本雜亂無章的一堆東西,按照某種順序排好,譬如說圖書館裡面的書籍,按照書籍的編號有小到大排好,譬如說醫院的病歷,按照病歷號碼有小到大排好,譬如說一堆檔案,按照字母順序或是檔案時間順序有早到晚排好,這些都是排序的應用。那麼電腦要如何完成「排序」(sort) 這件工作呢?「二元樹」 (binary tree) 怎樣子應用在排序這項工作呢?

Read Full Post »

Posted By Mr. Thursday 如果今天有一台機器,N個人要用,每個人使用的時間分別是t1, t2, …, tn,那麼怎樣子才能讓等待的時間最少呢?如果是以每個人的角度來說的話,當然是先搶先贏啦!不過如果是以這N個人所屬機構的角度來看,要讓全部人的等待時間最少,要如何安排使用機器的順序呢?這個時候作業系統 (OS: Operating System) 裡面的CPU Scheduling方法,就可以參考了! 首先我們先看看N個人不同的先後順序有幾種組合呢?答案是N!(N階層)種組合,譬如說5個人先後順序的組合方法就有5! = 120種組合,裡面包括第一個人先、然後第二個人、第三個人、第四個人、第五個人執行,也包括第一個人先、然後第三個人、第四個人、第五個人、最後才是第二個人執行,以及更多種組合的方法。因此我們排程的解答,就是在這麼多種組合(N!種)裡面,找到一個執行的順序,大家等待的時間加總起來是最小的。然而要怎麼找到這個解答呢?

Read Full Post »

想像一下,我剛才說了一句話,那句話是:「想像一下,我剛才說了一句話,那句話是:「想像一下,我剛才說了一句話,那句話是:……….」」,如此下去,就好像站在兩面平行擺設的鏡子中間,鏡子中的影像不斷的重複。再舉個例子,寫完一封信想要匿名保密,就署名「知名不具」。回信的人寫:「知知名不具 具」。之後再回信的時候就變成:知知知名不具具具,加上括號可能比較清楚:(知(知(知名不具)具)具)。

Read Full Post »