追蹤
愛瑋斯坦の冒險日記にようこそ
關於部落格
「星屑のなかで出會えた奇跡が 」
  • 182111

    累積人氣

  • 7

    今日人氣

    23

    追蹤人氣

複雜度與演算法-以尋找質數為例 (使用C++)






不好意思讓你眼花撩亂啦 (完全沒反省)

(其實我原本想貼到小於100萬的質數)

不過用photo impact一張一張剪貼真累,真是害人害己。


----------------------------------------------------------------------------


今天要談論的主題是複雜度與演算法-以尋找質數為例

聽起來很專業實際上我也只略懂皮毛,這是上課中老師稍微提到的概念

在進入正題之前之前,先介紹一下何謂複雜度(O)與質數



----------------------以下資料來自維基大百科--------------------------

大O符號(Big O notation)是用於描述函數漸進行為的數學符號。更確切地說,它是用另一個(通常更簡單的)函數來描述一個函數數量級的漸近上界。在數學中,它一般用來刻畫被截斷的無窮級數尤其是漸近級數的剩餘項;在電腦科學中,它在分析演算法複雜性的方面非常有用。

大O符號在分析演算法效率的時候非常有用。舉個例子,解決一個規模為 n 的問題所花費的時間(或者所需步驟的數目)可以被求得:T(n) = 4n² - 2n + 2。
 
當 n 增大時,n² 項將開始占主導地位,而其他各項可以被忽略——舉例說明:當 n = 500,4n² 項是 2n 項的1000倍大,因此在大多數場合下,省略後者對錶達式的值的影響將是可以忽略不計的。


簡單的說,就是當計算的規模越大的時候,此演算法(假設令為函數),


他的行為模式將被增長值最大的那一項主導 ,


例如微積分學到的級數概念(
n^n >> a^n >>n^2>>n>>ln n>>lnln n >>0,當n趨近於無限大的時候)


如果這樣還不懂,請看下面的例子!


以下的尋找質數實作將使用C++,並且使用4種稍微不同的演算法


-------------------------------------實作---------------------------------------

演算法一:暴力法
概念很簡單,就是將小於X的數字利用迴圈一個一個用蠻力去除,若除完每一個餘數都不等於0表示為質數,並把它印出來。
#include<iostream>
#include<time.h>
int main()
{  
    time_t start,end;
    int i,j,f,x;
   
    std::cout<<"請輸入X=";
    std::cin>>x;
   
    time(&start);
    
    for(i=2;i<=x;i++)
    {
         f=0;          
        for(j=2;j<i;j++)
        {
          if(i%j==0)
          {
           f=1;
           break;
          }
        } 
          if(f==0)
           std::cout<<i<<",";
    } 
    time(&end);
    std::cout<<"n本程式花了"<<difftime(end,start)<<"秒nn" ; 
    system("pause");
    return 0;
}
演算法二:根號法
上面的方法雖然簡單,但其實我們無形中多做了很多虛功,因為由簡單的代數證明就可以證明出要尋找質數只要從比X的根號值還小的數字去尋找就好,下面就是將尋找的範圍改成1~根號X
#include<iostream>
#include<time.h>
#include<math.h>
int main()
{  
    time_t start,end;
    int i,j,f,x;
   
    std::cout<<"請輸入X=";
    std::cin>>x;
   
    time(&start);
    
    for(i=2;i<=x;i++)
    {
         f=0;          
        for(j=2;j<=sqrt(i);j++)
        {
          if(i%j==0)
          {
           f=1;
           break;
          }
        }
       
          if(f==0)
           std::cout<<i<<",";
    }
   
    time(&end);
   
    std::cout<<"n本程式花了"<<difftime(end,start)<<"秒nn" ;
   
    system("pause");
    return 0;
}
            
演算法三:陣列法
不過上面的方法還有一個缺陷,就是當我們拿小於根號X的數字去除的時候,我們同時也會拿不是質數的數字去除,這句話是什麼意思呢?
例如我們要確認17是否為質數時,用上面的方法我們可能要拿2.3.4去除(2.3.4都小於根號17),可是當我們拿4去除的時候,4不是質數,他可以分解成因數2相乘,而我們在之前就用2去除過了,此時既然連4的因數都無法除盡了,更何況是4本身,這就是作虛功,這個效應剛開始看起來不明顯,但當X非常大的時候就會看出差異了,因此我們得出一個結論:
我們可以利用一個夠大的籃子(陣列),將每次找到的質數放進去,以後要判別一個數是否為質數的時候,我們只要從籃子(陣列)裡面挑出來的質數去除就好。
#include<iostream>
#include<time.h>
int main()
{  
    time_t start,end;
    int x,i,j,flag;
    int a[500000]={0};
  
std::cout<<"請輸入X=";
std::cin>>x;
   
    time(&start);
    
    for(i=2;i<=x;i++)
    {      
       flag=0;
       for(j=0;a[j]!=0;j++)   
         {   
             if(i%a[j]==0)
             {
               flag=1;
               break;
             } 
         }   
    
         if(flag==0)
          {      
          a[j]=i;       
          std::cout  <<i<<",";
          }       
     } 
    
     time(&end);
     std::cout<<"n本程式花了"<<difftime(end,start)<<"秒nn" ;
  
    system("pause");
    return 0;
}        


演算法四:陣列+根號法
其實這個就是將三和四的概念合在一起,沒什麼好講的@@
 
#include<iostream>
 #include<math.h>
 #include<time.h>
int main()
{  
    int count=0;
    time_t start,end;
    int x,i,j,k=1,flag;
    int a[500000]={2};
    
    std::cout<<"請輸入X=";
    std::cin>>x;
   
    time(&start);
   
    for(i=2;i<=x;i++)
    {                 
       flag=1;
       for(j=0;a[j]<=sqrt(i);j++)   
         {   
             if(i%a[j]==0)
             {
               flag=0;
               break;
             } 
          
         }   
    
        if(flag==1)
          {          
          a[k]=i;       
          std::cout  <<i<<",";
          k++;
          count++;
          }       
     } 
   
    time(&end);
    std::cout<<"n本程式花了"<<difftime(end,start)<<"秒nn" ;  
    std::cout<<"並且找到"<<count<<"個質數nn";
    system("pause");
    return 0;
}         


---------------------------------實作結束--------------------------------------

上面的程式碼其實不算是很重要,重點是歸納出結果,以下是利用不同演算法求解答所需的時間比較:


(以下為使用Intel Pentium 4  2.4Hz處理器得到的結果)


從上面我們可以知道X不大的時候各演算法時間差不多,但當X越來越大的時候,差距越來越大,同樣計算5百萬以內的質數,法1花了將近8個多小時!!!(31516秒),而法4才66秒,他X的害我電腦用100%的使用效率RUN了8小時由此就可看出孰優孰劣!


------------------------------------註一-------------------------------------


為什麼我在上面圖表特地用兩欄表示"質數個數"和(X/ln X)呢?


是因為我在尋找質數相關資料的時候,看到了所謂的"質數分布密度定理"


質數分布密度定理
小於或等於n的質數個數約等於n / loge n,換句話說,當我們任意挑選一個數n,且這個數n是質數的機率約等於1 / loge n;舉例來說,如果任意挑選一個100位數的整數,且挑到的整數又剛好是質數的機率約為(1 / ln 100)。

嗯~@@ 兩兩比較之後還真的很接近呢。。。。。。。抱歉又扯遠了


不好意思讓你/妳看了這麼密密麻麻外的文章,如果有機會的話我會繼續荼毒你的,謝謝你的支持           ...................以上

                          by 愛瑋斯坦
相簿設定
標籤設定
相簿狀態