• <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>

            Life is Good.

            Enhance Tech and English
            隨筆 - 65, 文章 - 20, 評論 - 21, 引用 - 0
            數據加載中……

            算法的時間復雜度

            求解算法的時間復雜度的具體步驟是:

              ⑴ 找出算法中的基本語句;

              算法中執行次數最多的那條語句就是基本語句,通常是最內層循環的循環體。

              ⑵ 計算基本語句的執行次數的數量級;

              只需計算基本語句執行次數的數量級,這就意味著只要保證基本語句執行次數的函數中的最高次冪正確即可,可以忽略所有低次冪和最高次冪的系數。這樣能夠簡化算法分析,并且使注意力集中在最重要的一點上:增長率。

              ⑶ 用大Ο記號表示算法的時間性能。

              將基本語句執行次數的數量級放入大Ο記號中。

              如果算法中包含嵌套的循環,則基本語句通常是最內層的循環體,如果算法中包含并列的循環,則將并列循環的時間復雜度相加。例如:

              for (i=1; i<=n; i++)
              x++;

              for (i=1; i<=n; i++)
              for (j=1; j<=n; j++)
              x++;

              第一個for循環的時間復雜度為Ο(n),第二個for循環的時間復雜度為Ο(n2),則整個算法的時間復雜度為Ο(n+n2)=Ο(n2)。

              常見的算法時間復雜度由小到大依次為:

              Ο(1)<Ο(log2n)<Ο(n)<Ο(nlog2n)<Ο(n2)<Ο(n3)<…<Ο(2n)<Ο(n!)

              Ο(1)表示基本語句的執行次數是一個常數,一般來說,只要算法中不存在循環語句,其時間復雜度就是Ο(1)。Ο(log2n)、Ο(n)、 Ο(nlog2n)、Ο(n2)和Ο(n3)稱為多項式時間,而Ο(2n)和Ο(n!)稱為指數時間。計算機科學家普遍認為前者是有效算法,把這類問題稱 為P類問題,而把后者稱為NP問題。

            O(1)

            Temp=i;i=j;j=temp;                     

            以 上三條單個語句的頻度均為1,該程序段的執行時間是一個與問題規模n無關的常數。算法的時間復雜度為常數階,記作T(n)=O(1)。如果算法的執行時 間不隨著問題規模n的增加而增長,即使算法中有上千條語句,其執行時間也不過是一個較大的常數。此類算法的時間復雜度是O(1)。 

            O(n^2)

            2.1. 交換i和j的內容
                 sum=0;                 (一次)
                 for(i=1;i<=n;i++)       (n次 )
                    for(j=1;j<=n;j++) (n^2次 )
                     sum++;       (n^2次 )
            解:T(n)=2n^2+n+1 =O(n^2)

            2.2.   
                for (i=1;i<n;i++)
                { 
                    y=y+1;         ①   
                    for (j=0;j<=(2*n);j++)    
                       x++;        ②      
                }          
            解: 語句1的頻度是n-1
                      語句2的頻度是(n-1)*(2n+1)=2n^2-n-1
                      f(n)=2n^2-n-1+(n-1)=2n^2-2
                      該程序的時間復雜度T(n)=O(n^2).         

            O(n)      
                                                                   
            2.3. 
                a=0;
                b=1;                      ①
                for (i=1;i<=n;i++) ②
                {  
                   s=a+b;    ③
                   b=a;     ④  
                   a=s;     ⑤
                }
            解: 語句1的頻度:2,        
                       語句2的頻度: n,        
                      語句3的頻度: n-1,        
                      語句4的頻度:n-1,    
                      語句5的頻度:n-1,                                  
                      T(n)=2+n+3(n-1)=4n-1=O(n).
                                                                                                              
            O(log2n)

            2.4.
                 i=1;      
                while (i<=n)
                   i=i*2;

            解: 語句1的頻度是1,
              
                      設語句2的頻度是f(n),   則:2^f(n)<=n;f(n)<=log2n    
                      取最大值f(n)= log2n,
                      T(n)=O(log2n )

            O(n^3)

            2.5. 
                for(i=0;i<n;i++)
                {  
                   for(j=0;j<i;j++)  
                   {
                      for(k=0;k<j;k++)
                         x=x+2;  
                   }
                }
            解: 當i=m, j=k的時候,內層循環的次數為k當i=m時, j 可以取 0,1,...,m-1 , 所以這里最內循環共進行了0+1+...+m-1=(m-1)m/2次所以,i從0取到n, 則循環共進行了: 0+(1-1)*1/2+...+(n-1)n/2=n(n+1)(n-1)/6所以時間復雜度為O(n^3).

            一個經驗規則

            有如下復雜度關系

            c < log2N < n < n * Log2N < n^2 < n^3 < 2^n < 3^n < n!

            其中c是一個常量,如果一個算法的復雜度為c 、 log2N 、n 、 n*log2N ,那么這個算法時間效率比較高 ,如果是 2^n , 3^n ,n!,那么稍微大一些的n就會令這個算法不能動了,居于中間的幾個則差強人意。

            posted on 2011-03-12 22:46 Mike Song 閱讀(7847) 評論(0)  編輯 收藏 引用

            久久久久人妻精品一区二区三区| 97久久超碰国产精品旧版| 久久久久久一区国产精品| 武侠古典久久婷婷狼人伊人| 亚洲va久久久噜噜噜久久狠狠| 久久久久久亚洲Av无码精品专口| AAA级久久久精品无码区| 久久久久久久综合狠狠综合| 99久久精品国产麻豆| 久久久久久A亚洲欧洲AV冫| 亚洲午夜久久久久久久久久| 99热精品久久只有精品| 人妻无码精品久久亚瑟影视| 青青国产成人久久91网| 久久妇女高潮几次MBA| 九九久久99综合一区二区| 久久婷婷五月综合97色直播| 久久最近最新中文字幕大全| 伊人精品久久久久7777| 亚洲欧美精品伊人久久| 中文精品久久久久人妻不卡| 免费一级做a爰片久久毛片潮| 99久久国产热无码精品免费| 麻豆精品久久久久久久99蜜桃| 国产三级观看久久| 久久91综合国产91久久精品| 久久国内免费视频| 久久一区二区三区免费| 狠狠色综合网站久久久久久久| 国产精品久久久久9999| 久久午夜伦鲁片免费无码| 狠狠综合久久AV一区二区三区| 久久综合成人网| 久久精品亚洲福利| 97精品国产97久久久久久免费| 久久国产精品成人免费| 丁香狠狠色婷婷久久综合| 精品久久久久久久久中文字幕| 999久久久无码国产精品| 久久精品国产亚洲AV无码娇色 | 国产精品VIDEOSSEX久久发布|