目錄

讓客戶滿意是我們工作的目標(biāo)，不斷超越客戶的期望值來自于我們對這個行業(yè)的熱愛。我們立志把好的技術(shù)通過有效、簡單的方式提供給客戶，將通過不懈努力成為客戶在信息化領(lǐng)域值得信任、有價值的長期合作伙伴，公司提供的服務(wù)項目有：域名注冊、網(wǎng)頁空間、營銷軟件、網(wǎng)站建設(shè)、陸川網(wǎng)站維護、網(wǎng)站推廣。

算法效率：

時間復(fù)雜度：

例題：

附加知識：

冒泡排序的時間復(fù)雜度求解：

二分查找的時間復(fù)雜度求解：

復(fù)雜度對比圖：

空間復(fù)雜度：

例題：

小結(jié)：

---

算法效率：

算法效率分析包括兩種：第一種時間效率（時間復(fù)雜度），第二種空間效率（空間復(fù)雜度）。時間效率被稱為時間復(fù)雜度而空間效率被稱作空間復(fù)雜度。 時間復(fù)雜度主要衡量的是一個算法的運行速度，而空間復(fù)雜度主要衡量一個算法所需要的額外空間，在計算機發(fā)展的早期，計算機的存儲容量很小。所以對空間復(fù)雜度很是在乎。但是經(jīng)過計算機行業(yè)的迅速發(fā)展，計算機的存儲容量已經(jīng)達(dá)到了很高的程度。所以我們?nèi)缃褚呀?jīng)不需要再特別關(guān)注一個算法的空間復(fù)雜度。

時間復(fù)雜度：

時間復(fù)雜度的定義: 在計算機科學(xué)中，算法的時間復(fù)雜度是一個函數(shù)，它定量描述了該算法的運行時間。算法中的基本操作的執(zhí)行次數(shù)，為算法的時間復(fù)雜。

推導(dǎo)大O階方法：

?????1、用常數(shù)1取代運行時間中的所有加法常數(shù)。

?????2、在修改后的運行次數(shù)函數(shù)中，只保留最高階項。

?????3、如果最高階項存在且不是1，則去除與這個項目相乘的常數(shù)。得到的結(jié)果就是大O階。

例題：

實例1：

// 請計算一下Func1基本操作執(zhí)行了多少次？
void Func1(int N)
{
 int count = 0;
 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);
}

可知第一個循環(huán)執(zhí)行n次，第二個循環(huán)執(zhí)行n^2次，第三個循環(huán)執(zhí)行10次。取它們中最高階的數(shù)來代表時間復(fù)雜度。這個就相當(dāng)于高數(shù)中的極限無窮小的比較。所以時間復(fù)雜度表示為O(N^2)。

實例2：

// 計算Func2的時間復(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í)行2*N+10次，根據(jù)第2、3項可知時間按復(fù)雜度為O(N)。

實例3：

// 計算Func3的時間復(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);
}

這個便需要根據(jù)N和M的具體關(guān)系來判斷時間復(fù)雜度。如果沒有具體條件，時間復(fù)雜度便是O(N+M)。當(dāng)N遠(yuǎn)大于M為O(N)。差不多的時候為O(M)/O(N)。

實例4：

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

若確定常數(shù)次，則為O(1)。

附加知識：

有些算法的時間復(fù)雜度存在最好、平均和最壞情況：

最壞情況：任意輸入規(guī)模的大運行次數(shù)(上界)

平均情況：任意輸入規(guī)模的期望運行次數(shù)

最好情況：任意輸入規(guī)模的最小運行次數(shù)(下界)

例如：在一個長度為N數(shù)組中搜索一個數(shù)據(jù)x

最好情況：1次找到

最壞情況：N次找到

平均情況：N/2次找到

在實際中一般情況關(guān)注的是算法的最壞運行情況，所以數(shù)組中搜索數(shù)據(jù)時間復(fù)雜度為O(N)。

冒泡排序的時間復(fù)雜度求解：

// 計算BubbleSort的時間復(fù)雜度？
void BubbleSort(int* a, int n)
{
 assert(a);
 for (size_t end = n; end >0; --end)
 {
     int exchange = 0;
     for (size_t i = 1; i< end; ++i)
     {
         if (a[i-1] >a[i])
     {
         Swap(&a[i-1], &a[i]);
         exchange = 1;
     }
 }
 if (exchange == 0)
 {
     break;
 }
}

最壞的情況便是冒泡排序的數(shù)列是最混亂的，每個數(shù)都需要交換。

第一次：N? 第二次：N-1? 第三次：N-2 …… 第N次：1。

所以我們發(fā)現(xiàn)這是一個等差數(shù)列：所以總次數(shù)為（N+1）*N/2.時間復(fù)雜度便為O(N^2).

二分查找的時間復(fù)雜度求解：

// 計算BinarySearch的時間復(fù)雜度？
int BinarySearch(int* a, int n, int x)
{
 assert(a);
 int begin = 0;
 int end = n;
 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;
 }
 return -1;
}

假設(shè)找了N次 則1*2*2*2……*2=N? 即2^X=N X=log2N。

因為很多地方不方便寫底數(shù)，所以時間復(fù)雜度便可以簡寫為O(logN)。

復(fù)雜度對比圖：

空間復(fù)雜度：

空間復(fù)雜度是對一個算法在運行過程中臨時占用存儲空間大小的量度 ?？臻g復(fù)雜度不是程序占用 了多少bytes的空間，因為這個也沒太大意義，所以空間復(fù)雜度算的是變量的個數(shù)?？臻g復(fù)雜度計 算規(guī)則基本跟實踐復(fù)雜度類似，也使用大O漸進表示法。

例題：

可知其一共五個變量所以空間復(fù)雜度為O(1)。

// 計算階乘遞歸Factorial的空間復(fù)雜度？
long long Factorial(size_t N)
{
 return N< 2 ? N : Factorial(N-1)*N;
}

遞歸調(diào)用了N層，每次調(diào)用建立一個棧幀，每個棧幀使用了常數(shù)個空間 ->0(1)
調(diào)用時，建立棧幀；返回時，銷毀。所以該程序空間復(fù)雜度為O(N)。

小結(jié)：

文章篇幅有限，故一些重點的算法題將在下一篇文章來說明，希望大家支持一下，給孩子個努力的動力！??！

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站題目：數(shù)據(jù)結(jié)構(gòu)——時間/空間復(fù)雜度-創(chuàng)新互聯(lián)
當(dāng)前路徑：http://weahome.cn/article/cseesi.html