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

網(wǎng)站建設(shè)哪家好，找創(chuàng)新互聯(lián)建站！專注于網(wǎng)頁設(shè)計(jì)、網(wǎng)站建設(shè)、微信開發(fā)、微信小程序定制開發(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語法里的函數(shù)。

      如下面這個代碼：

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 --)

          {

                    //...

          }

}

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

• 算法分析的分類

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

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

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

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

最壞情況:N次比較。

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

最好情況:1次比較。

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

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

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

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

算法分析要保持大局觀：

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

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

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

通常我們使用O記號法表示最壞運(yùn)行情況的漸進(jìn)上界。其實(shí)也就是說我們使用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)表示法。--（對象的個數(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;

}

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

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

這段代碼有下面幾個明顯缺陷：

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

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

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

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

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）。

方法二：用一個循環(huán)開辟一個數(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ù)個對象。

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

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

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

廣告

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