?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ???? ?? ??
??個(gè)人主頁 ：阿然成長日記 ??點(diǎn)擊可跳轉(zhuǎn)
?? 個(gè)人專欄： ??數(shù)據(jù)結(jié)構(gòu)與算法??C語言進(jìn)階
?? 不能則學(xué)，不知?jiǎng)t問，恥于問人，決無長進(jìn)
?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ?? ??

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

??1.1 時(shí)間復(fù)雜度的概念

· 時(shí)間復(fù)雜度的定義：在計(jì)算機(jī)科學(xué)中，算法的時(shí)間復(fù)雜度是一個(gè)函數(shù)，它定量描述了該算法的運(yùn)行時(shí)間。一個(gè)算法執(zhí)行所耗費(fèi)的時(shí)間，從理論上說，是不能算出來的，只有你把你的程序放在機(jī)器上跑起來，才能知 道。但是我們需要每個(gè)算法都上機(jī)測試嗎？是可以都上機(jī)測試，但是這很麻煩，所以才有了時(shí)間復(fù)雜度這個(gè)分析方式。一個(gè)算法所花費(fèi)的時(shí)間與其中語句的執(zhí)行次數(shù)成正比例，算法中的基本操作的執(zhí)行次數(shù)，為算法 的時(shí)間復(fù)雜度。

1.2 大O的漸進(jìn)表示法

大O符號(hào)（Big O notation）：是用于描述函數(shù)漸進(jìn)行為的數(shù)學(xué)符號(hào)。

??推導(dǎo)大O階方法：
1、O(1)用常數(shù)1取代運(yùn)行時(shí)間中的所有加法常數(shù)。
2、在修改后的運(yùn)行次數(shù)函數(shù)中， 只保留最高階項(xiàng)。
3、如果最高階項(xiàng)存在且不是1，則去除與這個(gè)項(xiàng)目相乘的常數(shù)。得到的結(jié)果就是大O階。
??常見時(shí)間復(fù)雜度：（ 復(fù)雜度由小到大）

??大O階的三種情況：
最壞情況：任意輸入規(guī)模的最大運(yùn)行次數(shù)(上界)
平均情況：任意輸入規(guī)模的期望運(yùn)行次數(shù)
最好情況：任意輸入規(guī)模的最小運(yùn)行次數(shù)(下界）
注：我們一般都取最壞的情況作為這個(gè)算法的時(shí)間復(fù)雜度。

??空間復(fù)雜度

·空間復(fù)雜度也是一個(gè)數(shù)學(xué)表達(dá)式，是對(duì)一個(gè)算法在運(yùn)行過程中臨時(shí)占用存儲(chǔ)空間大小的量度 。
·空間復(fù)雜度不是程序占用了多少bytes的空間，因?yàn)檫@個(gè)也沒太大意義，所以空間復(fù)雜度算的是變量的個(gè)數(shù)。
·空間復(fù)雜度計(jì)算規(guī)則基本跟實(shí)踐復(fù)雜度類似，也使用大O漸進(jìn)表示法。

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

??例題分析

1.案例（常數(shù)階）

int fun(int n)
{
  int i = 0;int cnt = 0;
   for( i; i<100;i++)
     {
       cnt++;
      }
  return cnt;
}

此時(shí)時(shí)間復(fù)雜度為O(1),這里的1不是指一次,而是常數(shù)次,該循環(huán)執(zhí)行了100次,不管n多大,他都執(zhí)行100次,所以是O(1)常數(shù)階。

2.案例（線性階）

分析下面代碼復(fù)雜度

// 計(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);
因?yàn)槲覀儾⒉恢繫和N誰大，所以我們不能舍棄任何一個(gè)。
假如:M無窮大，那么時(shí)間復(fù)雜度為O(M);反之亦然。

3.案例：（平方階）

分析下面代碼的時(shí)間復(fù)雜度

int fun(int n)
{
   int cnt = 0;
  for(int i = 0;i < n;i++)
   {
     for(int j = 0; j<n; j++)
      {
        cnt++; 
      }
   }//兩層循環(huán)，每次循環(huán)n次，因此為n*n
 
 
  for(int k = 0; k<n; k++)
   {
     ++cnt;
   }//一層循環(huán)，循環(huán)n次
  
  for(int l = 0;l<10;l++)
   {
     ++cnt;
   }//一層循環(huán)，循環(huán)10次
 
return cnt;
}

我們列出計(jì)算時(shí)間的復(fù)雜度的表達(dá)式：n*n +n +10。但是我們能寫成O(N*N+N+10嗎？我們知道，對(duì)于時(shí)間復(fù)雜度我們不需算出精確的數(shù)字，只需要算出這個(gè)算法屬于什么量級(jí)即可，我們又如何知道它屬于哪個(gè)量級(jí)呢？即，我們將字母取無窮大，例如本題中字母為n，n取無窮大，而十對(duì)于n取無窮大后沒有影響，因此10可以舍去，原表達(dá)式化為nn+n，再轉(zhuǎn)化為n(n+1)，由于n為無窮大，因此-1也是沒有影響的，原式就變成了O(N*N)=O(N^2)。
?? 在這里我們使用大O漸近表示法，只是一種量級(jí)的估算，而不是準(zhǔn)確的值。

4.案例（平方階）

分析冒泡排序的時(shí)間復(fù)雜度

void bubblesort(int* a,int n)
{
   assert(a);
for(int end = n; end>0; end--)
    {
      int exchange = 0;
       for(int i = 1; i<end; i++)
           {
              if(a[i-1]>a[i])
              {
                swap(&a[i],&a[i-1]);
                 exchange = 1;
               }
            }
    
       if(exchange==0)
           break;
     }
}

在這個(gè)冒泡排序中,我們需要將無序數(shù)組轉(zhuǎn)化為有序數(shù)組的一種算法,它并不是簡單的雙層嵌套循環(huán),很容易想到它的循環(huán)次數(shù)是一個(gè)等差數(shù)列,第一次循環(huán)n-1次,第二次n-2次…一直到1.因此為n-1+n-2+n-3…+1 =·n*(n-1)/2,使用大O表示，去掉影響不大的項(xiàng)，簡化為： 時(shí)間復(fù)雜度為O(N*N)。

5.案例（對(duì)數(shù)階）

二分查找

int binary(int n, int a[], int k) 
{
	int left = 0, right = n - 1;
	while(l <= r) {
		mid = (l + r)/2;
		if(a[mid] == k) 
		    return mid;
		else if(a[mid] < k)
			right = mid + 1;
		else
			left = mid + 1;
	}
	return -1;
}

eft和right指數(shù)組最左邊和最右邊的下標(biāo).每次將這個(gè)數(shù)組砍一半,求出mid中間下標(biāo). 由于是升序排列,如果中間下標(biāo)代表的數(shù)大于給定的數(shù)k,那么k必定在中間下標(biāo)的左邊. 那么就將mid+1的值賦給right,反之則將mid+1的值賦給left,每次將數(shù)組砍一半直到找到數(shù)k為止.
也就是每次除二。2^n=N -> n=logN;

6.案例（遞歸調(diào)用）

斐波那契函數(shù)

long long Fac(size_t N)
{
 if(N == 0)
 return 1;
 
 return Fac(N-1)*N;
}

推到知道，這個(gè)函數(shù)會(huì)不停的向下調(diào)用，呈金字塔型，雖然運(yùn)算量非常大，但是我們?cè)谒銜r(shí)間復(fù)雜度時(shí)要關(guān)注代碼的思想，而不是看它的次數(shù)等。 遞歸函數(shù)的時(shí)間復(fù)雜度是多次用的次數(shù)的累加。
空間復(fù)雜度：根據(jù)調(diào)用的次數(shù)，每次都會(huì)占用棧上的空間，所以間復(fù)雜度為O(N);

??總結(jié)：

不管是算時(shí)間復(fù)雜度，還是空間復(fù)雜度。我們都要根據(jù)代碼的思想，探求程序運(yùn)行的過程，來思考復(fù)雜度。不能片面的根據(jù)數(shù)量，次數(shù)的多少來算。文章來源地址http://www.zghlxwxcb.cn/news/detail-607088.html

到了這里，關(guān)于【數(shù)據(jù)結(jié)構(gòu)】---時(shí)間復(fù)雜度與空間復(fù)雜度的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！