舉例說(shuō)明時(shí)間復(fù)雜度與空間復(fù)雜度

什么是時(shí)間復(fù)雜度與空間復(fù)雜度？相信很多人對(duì)時(shí)間復(fù)雜度與空間復(fù)雜度的了解處于懵懂狀態(tài)，小編給大家總結(jié)了以下內(nèi)容。如下資料是關(guān)于復(fù)雜度與空間復(fù)雜度的內(nèi)容。

網(wǎng)站建設(shè)哪家好，找創(chuàng)新互聯(lián)建站！專注于網(wǎng)頁(yè)設(shè)計(jì)、網(wǎng)站建設(shè)、微信開(kāi)發(fā)、微信小程序定制開(kāi)發(fā)、集團(tuán)企業(yè)網(wǎng)站建設(shè)等服務(wù)項(xiàng)目。為回饋新老客戶創(chuàng)新互聯(lián)還提供了新建免費(fèi)建站歡迎大家使用！

1、時(shí)間復(fù)雜度

      所謂時(shí)間復(fù)雜度實(shí)際上就是函數(shù)，既是函數(shù)計(jì)算執(zhí)行的基本操作次數(shù)。ps:這里的函數(shù)是指數(shù)學(xué)里面的函數(shù)，而不是C語(yǔ)法里的函數(shù)。

      如下面這個(gè)代碼：

void Test1 ( int N )

{

           for (int i = 0; i < N ; ++ i)

          {

                    for (int j = 0; j < N ; ++ j)

                   {

                              //...

                   }

          }

           for (int k = 0; k < 2 * N ; ++ k)

          {

                    //...

          }


           int count = 10;

           while (count --)

          {

                    //...

          }

}

舉例說(shuō)明時(shí)間復(fù)雜度與空間復(fù)雜度

所以這段代碼的時(shí)間復(fù)雜度是： F(N) = N^2 + 2N + 10，這個(gè)時(shí)間計(jì)算的就是時(shí)間復(fù)雜度。

  • 算法分析的分類

  1. 最壞情況：任意輸入規(guī)模的最大運(yùn)行時(shí)間。（上界）

  2. 平均情況：任意輸入規(guī)模的期望運(yùn)行時(shí)間。

  3. 最好情況：任意輸入規(guī)模的最小運(yùn)行時(shí)間，通常最好情況不會(huì)出現(xiàn)。（下界）

例如：在一個(gè)長(zhǎng)度為N的線性表中搜索一個(gè)數(shù)據(jù)x。

最壞情況:N次比較。

平均情況:N/2次比較。

最好情況:1次比較。


在實(shí)際中我們通常情況考量的是算法的最壞運(yùn)行情況。也就是說(shuō)對(duì)于任意輸入規(guī)模N，算法的最長(zhǎng)運(yùn)行時(shí)間，理由如下：

  1. 一個(gè)算法的最壞情況的運(yùn)行時(shí)間是在任意輸入下的運(yùn)行時(shí)間上界。

  2. 對(duì)于某些算法，最壞的情況出現(xiàn)的較為頻繁。

  3. 大體上看，平均情況與最壞情況一樣差。

算法分析要保持大局觀：

  1. 忽略掉那些的常數(shù)。

  2. 關(guān)注運(yùn)行時(shí)間的增長(zhǎng)趨勢(shì)，關(guān)注函數(shù)式中增長(zhǎng)最快的表達(dá)式。



  • O的漸進(jìn)表示法（Big O Notation）

通常我們使用O記號(hào)法表示最壞運(yùn)行情況的漸進(jìn)上界。其實(shí)也就是說(shuō)我們使用O標(biāo)記法表示時(shí)間復(fù)雜度，一般關(guān)注的是算法運(yùn)行的最壞情況。


下面我們使用大O的漸進(jìn)表示法計(jì)算下面函數(shù)的時(shí)間復(fù)雜度


如：F(N) = N^3 + N^2 + N +1000,則關(guān)注N^3->O(N^3)



  • 【1.一般算法的時(shí)間復(fù)雜度計(jì)算】

void Test1 ( int N )

{

           for (int i = 0; i < N ; ++ i)

          {

                    for (int j = 0; j < N ; ++ j)

                   {

                              //...

                   }

          }


           for (int k = 0; k < 2 * N ; ++ k)

          {

                    //...

          }


           int count = 10;

           while (count --)

          {

                    //...

          }

}

Test1的時(shí)間復(fù)雜度為：O(N^2)


void Test2 (int N, int M)

{

           for (int i = 0; i < M ; ++i)

          {

          }


           for (int k = 0; k < N ; ++k)

          {

                    //...

          }

}

Test2的時(shí)間復(fù)雜度為：O(M+N)


void Test3 (int N, int M)

{

           for (int i = 0; i < M ; ++i)

          {

                    for (int j = 0; j < N ; ++j)

                   {

                              //...

                   }

          }

}

Test3的時(shí)間復(fù)雜度為：O(M*N)

【2.遞歸算法的時(shí)間復(fù)雜度計(jì)算】


遞歸算法的時(shí)間復(fù)雜度為遞歸總次數(shù)*每次遞歸次數(shù)。



  • 空間復(fù)雜度

空間復(fù)雜度的計(jì)算跟時(shí)間復(fù)雜度類似，也使用大O的漸進(jìn)表示法。--（對(duì)象的個(gè)數(shù)）

要注意的是遞歸算法的空間復(fù)雜度，假如遞歸深度為N*每次遞歸的空間大小為1，則空間復(fù)雜度為O(N)。

 以斐波那契數(shù)列為例：

#include<iostream>

#include<stdlib.h>

using namespace std;


//斐波那契數(shù)列的遞歸算法(一般解法)


int Fib(int N )

{

             return N < 2 ? N : Fib( N - 1) + Fib( N - 2);

}


int main()

{


             int ret=Fib(0);

            cout << ret << endl;

            system( "pause");

             return 0;

}

舉例說(shuō)明時(shí)間復(fù)雜度與空間復(fù)雜度舉例說(shuō)明時(shí)間復(fù)雜度與空間復(fù)雜度

此代碼的空間復(fù)雜度是：O（N），既是深度。

             時(shí)間復(fù)雜度是：O（2^N）.

這段代碼有下面幾個(gè)明顯缺陷：

1、遞歸時(shí)會(huì)有函數(shù)的壓棧開(kāi)銷。

2、有重復(fù)計(jì)算。

    所以我們需要對(duì)這段代碼進(jìn)行優(yōu)化。請(qǐng)看下面：

方法一：可以倒著計(jì)算，定義三個(gè)變量，如下所示：

long long Fib(size_t N )

{

             long long * Fibarray = new long long[ N + 1];

            Fibarray[0] = 0;

            Fibarray[1] = 1;


             for ( int i = 2; i <= N; ++i)

            {

                        Fibarray[i] = Fibarray[i - 1] + Fibarray[i - 2];

            }


             long long ret = Fibarray[ N];

             delete[] Fibarray;


             return ret;

}

此方法的時(shí)間復(fù)雜度為：O（N）。

            空間復(fù)雜度為：O（N）。

方法二：用一個(gè)循環(huán)開(kāi)辟一個(gè)數(shù)組。

long long Fib(size_t N )

{

             long long Fib[3] = { 0, 1, N };

             for ( int i = 2; i <= N; ++i)

            {

                        Fib[2] = Fib[1] + Fib[0];

                        Fib[0] = Fib[1];

                        Fib[1] = Fib[2];

            }

             return Fib[2];

}

這種方法的時(shí)間復(fù)雜度是：O（N）。

       空間復(fù)雜度是：O（1），因?yàn)槌?shù)個(gè)對(duì)象。


看完上訴內(nèi)容，你們對(duì)時(shí)間復(fù)雜度與空間復(fù)雜度大概了解了嗎？如果想了解更多相關(guān)文章內(nèi)容，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝各位的閱讀！

名稱欄目：舉例說(shuō)明時(shí)間復(fù)雜度與空間復(fù)雜度
URL鏈接：http://muchs.cn/article36/gppdpg.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供商城網(wǎng)站、服務(wù)器托管、全網(wǎng)營(yíng)銷推廣、企業(yè)建站、動(dòng)態(tài)網(wǎng)站、網(wǎng)站收錄

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)

手機(jī)網(wǎng)站建設(shè)