基本程式演算法  
     
     
  甚麼是演算法  
     
    演算法是將原始的資訊,經由一種判斷、數學計算或是歸類準則等,輸出為我們需要的資訊的方法。    
    原始的資訊我們稱之為輸入(Input),計算、判斷或是歸類的結果,我們稱之為輸出(Output)。    
                 
     

     
                 
    例如圍棋的演算法,輸入了目前的棋步後,經由演算法計算出下一步對應的棋步。    
                 
     

     
                 
      又例如計算成績的演算法,輸入了各科及所有人的分數後,經由演算法計算出每個人的總分以及排名。      
                 
     

     
                 
      演算法並非程式語言,而可能是一種思考的流程或是數學的方程式,程式語言只是將這樣的思考及處理流程實現出結果的方法之一。如果要使用程式來實現計算分析或是某種功能,我們必須先思考出合適的演算法,再把演算法轉換成程式。      
       

 

       
  演算法的類別  
                 
    基本的演算法    
                 
      1. 堆疊      
      2. 佇列      
      3. 資料結構      
      4. 排序      
      5. 搜尋      
      6. 求方程式解      
             
    進階的演算法    
             
      1. 方程式計算      
      2. 統計      
      3. 濾波      
      4. 通訊      
      5. 壓縮      
      6. 自動控制      
      7. 視覺      
      8. 人工智慧      
             
  時間複雜度與空間複雜度  
             
    演算法的好壞,最基本指標有兩個:    
             
    時間複雜度    
      時間複雜度的意義是這個演算法的計算有多快。      
                 
      時間複雜度是用來評斷演算法執行快慢的指標,因為很多的演算法使用在需要高速執行的場合,比方飛彈上用來偵測目標導引飛行方向的演算法,需要很高的計算速度才能準確擊中目標。      
      很多演算法是要用來進行非常複雜的演算,例如計算氣象資料的演算法就需要很長的時間,因此需要縮減計算的時間。      
      演算法有多快不是以秒來衡量,而是以計算需要的步驟及次數。      
             
      典型的例子是傅立葉轉換(Fourier Transform),數學上發展出很多種傅立葉轉換的計算方式,如離散傅立葉轉換(Discrete Fourier Transform,簡稱DFT)以及快速傅立葉轉換(Fast Fourier Transform,簡稱FFT),這兩者需要的計算次數就差異很大,如下表示一個以硬體執行計算的例子,標示出DFT與FFT的計算次數,在執行512個輸入樣本數的情形下,DFT需要262144次的執行次數,FFT則只需要2304次。這表示使用FFT計算時只需要使用DFT時的1/113的時間。      
             
     

     
                 
    空間複雜度    
      空間複雜度的意義這個演算法需要用到的記憶體有多少。      
             
      記憶體分為兩種使用的情形,一種是程式本身所佔用的記憶體(ROM),就是程式碼有多大。另一種是程式執行時,需要使用到的暫存記憶體(RAM)有多大。      
      在許多的應用場合中,ROM與RAM的大小都有嚴格的限制,很多的控制器中因為只能夠使用成本很低的MPU,所以只有限的記憶體能夠使用,例如冷氣機、遙控器中的MPU。      
      很多的應用裡,是因為有嚴格的重量限制,例如太空船、飛機,飛彈等,無法裝載太大型的計算機,因此也會限制計算機的計算速度與記憶體大小,因此就需要盡量減少記憶體的使用。      
             
      典型的例子也是傅立葉轉換(Fourier Transform),DFT的計算需要使用到遞迴,在執行512個輸入樣本數的情形下,DFT大約需要使用到(基本變數量)x512的記憶體,FFT則只需要(基本變數量)x2就能夠進行計算,這表示使用FFT計算時只需要使用DFT時的1/256的記憶體      
      因此僅需要使用小很多的計算機及記憶體,就能夠進行FFT的計算了。      
     

 

     
  Swap數值交換演算法  
             
    我們經常需要將兩個數值進行交換的場合,例如在排序中,我們需要改變數值排列的順序,因此需要不斷地在個數值之間進行數值的交換。    
         
    最簡單的排序方法如下圖,依據圖中所示的步驟,便可將兩個數值進行交換。    
                 
     

     
                 
  Sorting排序演算法  
                 
    甚麼是排序演算法    
                 
      排序(sorting),是將一組資料依照使用者需求,予以重新排列其順序。一般會依資料之大小順序排序(由大至小、或由小至大)。排序後之資料,較為容易閱讀、進行統計分析與快速搜尋。      
             
     

     
             
    氣泡排序法(Bubble Sorting)    
             
     

     
             
  Search搜尋演算法  
             
    甚麼是搜尋演算法    
             
      搜尋是在一堆資料中找出所要之特定資料。搜尋時會進襲大量的比較以找到特定的資料,當資料量較少時比較的次數少,很容易能夠尋找到特定的資料,但當資料量龐大時,需要的比較次數就會浪費大量的時間,因此有許多快速搜尋的方法來增加搜尋的效率。      
             
      一般資料的搜尋,都是先進行排序後,再使用搜尋法來搜尋特定的資料,排序過後的資料能夠令搜尋效率極高。      
             
     

     
             
    循序搜尋法(Sequential Search)    
                 
      從第一個資料開始比較是否為欲尋找的特定資料,依序一一比較,直到找到所要尋找的特定資料為止。    
                 
      優點      
                 
        程式容易撰寫。        
        資料不須事先排序。        
                 
      缺點    
                 
        搜尋效率比較差(平均次數=(N+1)/2)。        
        不管是否有排序,每次都必須要從頭到尾尋找一次。        
                 
     

     
                 
    二分搜尋法(Binary Search)    
                 
      二分法是將資料分成兩部份,再將鍵值與中間值比較,如鍵值相等則找到特定資料,小於鍵值時向前半段繼續比較,大於鍵值時則往後半段進行比較,如此,分段比較至尋找到特定資料為止。      
             
      優點      
                 
        搜尋效率佳(平均次數=Log2N)。        
                 
      缺點      
                 
        資料必需事先排序。        
        檔案資料必需使是可直接存取或隨機檔。        
                 
     

     
                 
                 
     
     
     
     
     
     
     
     
     
     
     
     
   

威宇嵌入式科技股份有限公司

新北市三峽區愛國路198號1樓

電話 : 02-26737160 傳真 : 02-26738712

 

 

CopyRight Cat Embedded Vision System Co.,Ltd. ,All rights reserved.

 
 

樹莓派 Pythonx Raspberry Pi 教學 課程機器人教學套件 電子套件 電路套件 電子實習 電學套件 避障車 108課綱 程式設計 創客 智慧機器人 彈性自主學習 積木套件 益智玩具 演算法 校園營隊 社團活動 編程 多元學習 DIY 平價套件 CEVT 科學教育實作 積木教材 教學資源線上下載 應用教學 BBC 機構組裝電路程式手冊 Python程式教學 MicroBit教學 自動控制 電機 資工 機械 MicroBit套件課程 PT套件 MicroBit演算法 自動控制概論程式技巧 教學套件 感測及控制元件機器人 教學套件 電子套件 電路套件 電子實習 電學套件