欧美vvv,亚洲第一成人在线,亚洲成人欧美日韩在线观看,日本猛少妇猛色XXXXX猛叫

@[toc]

算法的時(shí)間復(fù)雜度與空間復(fù)雜度

反爬鏈接

1. 算法效率

引：如何衡量一個(gè)算法的好壞呢？

算法在編譯鏈接成可執(zhí)行程序后，運(yùn)行時(shí)需要耗費(fèi)時(shí)間資源和空間(內(nèi)存)資源 。因此衡量一個(gè)算法的好壞，一般是從時(shí)間和空間兩個(gè)維度來衡量的，即時(shí)間復(fù)雜度和空間復(fù)雜度。

時(shí)間復(fù)雜度主要衡量一個(gè)算法的運(yùn)行快慢，而空間復(fù)雜度主要衡量一個(gè)算法運(yùn)行所需要的額外空間。

在計(jì)算機(jī)發(fā)展的早期，計(jì)算機(jī)的存儲容量很小。所以對空間復(fù)雜度很是在乎。但是經(jīng)過計(jì)算機(jī)行業(yè)的迅速發(fā)展，計(jì)算機(jī)的存儲容量已經(jīng)達(dá)到了很高的程度（摩爾定律：硬件每18個(gè)月翻倍）。所以我們?nèi)缃褚呀?jīng)不需要再特別關(guān)注一個(gè)算法的空間復(fù)雜度，重點(diǎn)關(guān)注時(shí)間復(fù)雜度。

2. 時(shí)間復(fù)雜度2.1 時(shí)間復(fù)雜度的概念在計(jì)算機(jī)科學(xué)中，算法的時(shí)間復(fù)雜度是一個(gè)函數(shù)（是含未知數(shù)的數(shù)學(xué)表達(dá)式啦hh），它定量描述了該算法的運(yùn)行時(shí)間。

計(jì)算時(shí)間復(fù)雜度不是計(jì)算時(shí)間。一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間，理論上是不能算出來的，只有你把你的程序放在機(jī)器上跑起來，才能知道。但是我們?nèi)绻總€(gè)算法都上機(jī)測試算法的時(shí)間復(fù)雜性tn，就很麻煩；且運(yùn)行環(huán)境不同，花費(fèi)時(shí)間也不同。

一個(gè)算法所花費(fèi)的時(shí)間與其中語句的執(zhí)行次數(shù)成正比例，算法中的基本操作的執(zhí)行次數(shù)，為算法的時(shí)間復(fù)雜度。

即：找到某條基本語句與問題規(guī)模N之間的數(shù)學(xué)表達(dá)式，就是算出了該算法的時(shí)間復(fù)雜度。

2.2 大O漸進(jìn)表示法:key:大O漸進(jìn)表示法用常數(shù)1表示運(yùn)行次數(shù)中所有加法常數(shù)在修改后的運(yùn)行次數(shù)的函數(shù)中，只保留最高階項(xiàng)。如果最高階存在且不為1，則去除與此項(xiàng)的系數(shù)。

例 ——

// 請計(jì)算一下Func1中++count語句總共執(zhí)行了多少次？
void Func1(int N) 
{
    int count = 0;
    for (int i = 0; i < N ; ++ i) 
    {
         for (int j = 0; j < N ; ++ j)
         {
             ++count;
         }
    }
 
    for (int k = 0; k < 2 * N ; ++ k)
    {
         ++count; 
    }
    
    int M = 10;
    while (M--) 
    {
         ++count; 
    }
    printf("%d\n", count);
}

Func1的基本執(zhí)行次數(shù)：

$$F(N) = N^2 + 2N + 10$$

NF(N) = N^2 + 2*N + 10N^2

N = 10

130

100

N = 100

1,0210

1,0000

N = 1000

100,2010

100,0000

由上表可以看出，N越大，后兩項(xiàng)對于結(jié)果的影響越小。因此，保留對結(jié)果影響最大的項(xiàng)，即可代表大概的執(zhí)行次數(shù)。

計(jì)算時(shí)間復(fù)雜度時(shí)，無需計(jì)算精確次數(shù)，只需要計(jì)算大概的執(zhí)行次數(shù)，那么這里我們使用大O的漸進(jìn)表示法（Big O ：用來描述函數(shù)漸進(jìn)行為的數(shù)學(xué)符號）。—— 估算

::因此，用大O漸進(jìn)表示法后，F(xiàn)unc1的時(shí)間復(fù)雜度為：

$$O(N^2)$$

2.3 常見時(shí)間復(fù)雜度計(jì)算實(shí)例

我們在練習(xí)中感受 ——

實(shí)例1 ——

// 計(jì)算Func2的時(shí)間復(fù)雜度？
void Func2(int N) 
{
     int count = 0;
    for (int k = 0; k < 2 * N ; ++ k)
     {
         ++count;
     }
    
     int M = 10;
    while (M--)
     {
         ++count;
     }
     printf("%d\n", count);
}

基本執(zhí)行次數(shù) ——

$$F(N) = 2*N+10$$

保留最高項(xiàng)，并去掉最高項(xiàng)系數(shù)后得

::時(shí)間復(fù)雜度 ——

$$O(N)$$

實(shí)例2 ——

// 計(jì)算Func3的時(shí)間復(fù)雜度？
void Func3(int N, int M) 
{
     int count = 0;
     for (int k = 0; k < M; ++ k)
     {
         ++count;
     }
     for (int k = 0; k < N ; ++ k)
     {
        ++count;
     }
    printf("%d\n", count);
}

若題目有條件，

::這里沒有說明，因此時(shí)間復(fù)雜度 ——

$$O(M+N)$$

實(shí)例3 ——

// 計(jì)算Func4的時(shí)間復(fù)雜度？
void Func4(int N) 
{
     int count = 0;
     for (int k = 0; k < 100; ++ k)
     {
         ++count;
     }
     printf("%d\n", count);
}

基本執(zhí)行次數(shù) ——

$$F(N) = 100$$

常數(shù)項(xiàng)用1代替后得

::時(shí)間復(fù)雜度 ——

$$O(1)$$

當(dāng)題目中要求，將時(shí)間復(fù)雜度優(yōu)化至O(1)，不是代表運(yùn)算一次，而是常數(shù)次。

實(shí)例4 —— 時(shí)間復(fù)雜度是做悲觀預(yù)期

// 計(jì)算strchr的時(shí)間復(fù)雜度？--由strstr聯(lián)想，這是在字符串中查找字符的庫函數(shù)
const char* strchr ( const char* str, int character );

const char* strchr ( const char* str, int character )
{
    while(*str != '\0')
    {
        if(*str == character)
        {
            return str;
        }
        str++;
    }
    return NULL;
}

當(dāng)隨著代碼的輸入不同，時(shí)間復(fù)雜度不同 ——

(例如：在一個(gè)長度為N數(shù)組中搜索一個(gè)數(shù)據(jù)x) hello world\0

要明白時(shí)間復(fù)雜度是做悲觀預(yù)期，看最壞情況。

::因此，這段代碼的時(shí)間復(fù)雜度為 ——

$$O(N)$$

:key:計(jì)算時(shí)間復(fù)雜度，要會用思想計(jì)算

接下來再來看兩段代碼 ——

實(shí)例5 —— 冒泡排序·思想計(jì)算

// 計(jì)算BubbleSort的時(shí)間復(fù)雜度？
void BubbleSort(int* a, int n) 
{
     assert(a);
     for (size_t end = n; end > 0; --end)
     {
        int flag = 0;
        for (size_t i = 1; i < end; ++i)

        {
            if (a[i-1] > a[i])
            {
                Swap(&a[i-1], &a[i]);
                flag = 1;
            }
         }
         if (flag == 0)
         break;
        }
}

這里不能因?yàn)榍短琢藘蓪友h(huán)，就簡單的認(rèn)為時(shí)間復(fù)雜度為O(N)

思想分析 —— $N$個(gè)數(shù)字，共排$N-1$趟，每一趟進(jìn)行$N-i-1$次比較（第$i$趟，$i= 0,1,2...$），這過程太熟悉了，就不贅述了

最壞的情況（由等差數(shù)列公式）:

$$F(N) = (N-1)+(N-2)+...+2+1 = (N-1+1)(N-1)/2$$

最好的情況（已經(jīng)有序）:

$$F(N) = N-1$$

因此冒泡排序的時(shí)間復(fù)雜度為

$$O(N^2)$$

實(shí)例6 —— 二分查找·思想計(jì)算

// 計(jì)算BinarySearch的時(shí)間復(fù)雜度？
int BinarySearch(int* a, int n, int x) 
{
    assert(a);
    int begin = 0;
    int end = n - 1;
    while (begin < end)
    {
        int mid = begin + ((end - begin) >> 1);
        
        if (a[mid] < x)
            begin = mid + 1;
        else if (a[mid] > x)
            end = mid;
        else
            return mid - 1;
    }
    return -1;
}

因此，二分查找的時(shí)間復(fù)雜度為

$$O(logN)$$

如果我要在14億人口中查找一個(gè)人，用二分查找要查找?guī)状危?/p>

N個(gè)數(shù)中查找能查找的人數(shù)查找次數(shù)

2^10

1024

10

2^20

100w

20

2^30

10億

30（變化很不明顯）

只需要查找31次。

這里我們要認(rèn)識到二分查找還算是很nb的算法，當(dāng)然了，排成有序也是有消耗的。

實(shí)例7、8-—— 遞歸·時(shí)間復(fù)雜度計(jì)算:key:遞歸算法計(jì)算時(shí)間復(fù)雜度：

$$O(N) = 遞歸次數(shù)*每次遞歸調(diào)用中的次數(shù)$$

每次遞歸調(diào)用中的次數(shù)是指 —— 一次遞歸調(diào)用中，基本操作的次數(shù)。

// 計(jì)算階乘遞歸Fac的時(shí)間復(fù)雜度？
long long Fac(size_t N)
{
    if (0 == N)
        return 1;
    return Fac(N - 1)*N;
}

下一個(gè) ——

//計(jì)算斐波那契額數(shù)列Fib遞歸的時(shí)間復(fù)雜度
long long Fib(size_t N)
{
    if(N < 3)
        return 1;
    
    return Fib(N-1) + Fib(N-2);
}

因此算法的時(shí)間復(fù)雜性tn，時(shí)間復(fù)雜度為 ——

$$O(2^N)$$

實(shí)際上，斐波那契額數(shù)列的遞歸寫法我們基本不用，因?yàn)樘耍捎玫蚾kk

3. 空間復(fù)雜度

空間復(fù)雜度也是一個(gè)數(shù)學(xué)表達(dá)式，是對一個(gè)算法在運(yùn)行過程中臨時(shí)額外占用存儲空間大小的量度 。

空間復(fù)雜度不是程序占用了多少bytes的空間，因?yàn)檫@個(gè)也沒太大意義，所以空間復(fù)雜度算的是變量的個(gè)數(shù)。

空間復(fù)雜度計(jì)算規(guī)則基本跟時(shí)間復(fù)雜度類似，也使用大O漸進(jìn)表示法。

注意：函數(shù)運(yùn)行時(shí)所需要的棧空間(存儲參數(shù)、局部變量、一些寄存器信息等)在編譯期間已經(jīng)確定好了，因此空間復(fù)雜度主要通過函數(shù)在運(yùn)行時(shí)候顯式申請的額外空間來確定。

實(shí)例1 ——

// 計(jì)算BubbleSort的空間復(fù)雜度？
void BubbleSort(int* a, int n) 
{
    assert(a);
    for (size_t end = n; end > 0; --end)
    {
        int flag = 0;
        for (size_t i = 1; i < end; ++i)
        {
            if (a[i - 1] > a[i])

            {
                Swap(&a[i - 1], &a[i]);
                flag = 1;
            }
        }
        if (flag == 0)
            break;
    }
}

::因此空間復(fù)雜度為 ——

$$O(1)$$

實(shí)例2 ——

// 計(jì)算Fibonacci的空間復(fù)雜度？
// 返回斐波那契數(shù)列的前n項(xiàng)
long long* Fibonacci(size_t n)
{
    if (n == 0)
        return NULL;
    long long* fibArray = (long long*)malloc((n + 1) * sizeof(long long));
    fibArray[0] = 0;
    fibArray[1] = 1;
    for (int i = 2; i <= n; ++i)
    {
        fibArray[i] = fibArray[i - 1] + fibArray[i - 2];
    }
    return fibArray;

::空間復(fù)雜度為 ——

$$O(N)$$

時(shí)間復(fù)雜度為 ——

$$O(N)$$

當(dāng)然，如果只是要求斐波那契數(shù)列中的第n個(gè)數(shù)，那就不需要額外申請n個(gè)空間，空間復(fù)雜度即為 ——

$$O(1)$$

實(shí)例3 ——

如何計(jì)算階乘遞歸的空間復(fù)雜度？—— 遞歸深度

// 計(jì)算階乘遞歸Fac的空間復(fù)雜度？long long Fac(size_t N) 
{     
    if(N == 0)
             return 1;
                  return Fac(N-1)*N; }

::因此空間復(fù)雜度為 ——

$$O(N)$$

4. 常見復(fù)雜度的對比:key:時(shí)間復(fù)雜度不計(jì)算時(shí)間，計(jì)算大概運(yùn)算次數(shù)

:key:空間復(fù)雜度不計(jì)算空間，計(jì)算大概定義變量的個(gè)數(shù)

這里要對各種時(shí)間復(fù)雜度的好壞有認(rèn)知。