一、時(shí)間復(fù)雜度：（注意：不是指程序運(yùn)行時(shí)間）
1定義：一般情況下，算法中基本操作重復(fù)執(zhí)行的次數(shù)是問(wèn)題規(guī)模n的某個(gè)函數(shù)，用T(n)表示，若有某個(gè)輔助函數(shù)f(n),使得當(dāng)n趨近于無(wú)窮大時(shí)，T（n)/f(n)的極限值為不等于零的常數(shù)，則稱f(n)是T(n)的同數(shù)量級(jí)函數(shù)。記作T(n)=Ｏ(f(n)),稱Ｏ(f(n)) 為算法的漸進(jìn)時(shí)間復(fù)雜度，簡(jiǎn)稱時(shí)間復(fù)雜度。
2、 計(jì)算方法：在計(jì)算時(shí)間復(fù)雜度的時(shí)候，先找出算法的基本操作，然后根據(jù)相應(yīng)的各語(yǔ)句確定它的執(zhí)行次數(shù)，再找出 T(n) 的同數(shù)量級(jí)（它的同數(shù)量級(jí)有以下：1，log2n，n，n log2n ，n的平方，n的三次方，2的n次方，n!），找出后，f(n) = 該數(shù)量級(jí)，若 T(n)/f(n) 求極限可得到一常數(shù)c，則時(shí)間復(fù)雜度T(n) = O(f(n))
二、空間復(fù)雜度（注意：不是計(jì)算空間，而是指對(duì)象的個(gè)數(shù)）
1、空間復(fù)雜度是對(duì)一個(gè)算法在運(yùn)行過(guò)程中臨時(shí)占用存儲(chǔ)空間大小的量度，記做S(n)=O(f(n))。比如直接插入排序的時(shí)間復(fù)雜度是O(n^2),空間復(fù)雜度是O(1) 。而一般的遞歸算法就要有O(n)的空間復(fù)雜度了，因?yàn)槊看芜f歸都要存儲(chǔ)返回信息。一個(gè)算法的優(yōu)劣主要從算法的執(zhí)行時(shí)間和所需要占用的存儲(chǔ)空間兩個(gè)方面衡量。
三、來(lái)幾段代碼大概解釋以上兩個(gè)問(wèn)題
折半查找法–非遞歸法
int BiSearch(int *arr,int len,int k)
{ int left = 0; int right = len; int mid = 0; while (right>=left)
{ mid=left+((right-left)>>1); if (k>arr[mid])
{ left=mid+1;
} else if (k<arr[mid])
{ right=mid-1;
} else return mid;
}
return -1;
} int main ()
{ int arr[]={1,2,3,4,5,6,7,8,9}; int k = 0; int len = sizeof(arr)/sizeof(arr[0])-1;
printf("arr[%d]\n", BiSearch(arr,len,1)) ;
printf("arr[%d]\n", BiSearch(arr,len,2)) ;
printf("arr[%d]\n", BiSearch(arr,len,3)) ;
printf("arr[%d]\n", BiSearch(arr,len,4)) ;
printf("arr[%d]\n", BiSearch(arr,len,5)) ;
printf("arr[%d]\n", BiSearch(arr,len,6)) ;
printf("arr[%d]\n", BiSearch(arr,len,7)) ;
printf("arr[%d]\n", BiSearch(arr,len,8)) ;
printf("arr[%d]\n", BiSearch(arr,len,9)) ;
printf("arr[%d]\n", BiSearch(arr,len,10)) ;
printf("arr[%d]\n", BiSearch(arr,len,0)) ;
return 0;
}
-
1
-
2
-
3
-
4
-
5
-
6
-
7
-
8
-
9
-
10
-
11
-
12
-
13
-
14
-
15
-
16
-
17
-
18
-
19
-
20
-
21
-
22
-
23
-
24
-
25
-
26
-
27
-
28
-
29
-
30
-
31
-
32
-
33
-
34
-
35
-
36
-
37
-
38
-
39
-
40
-
41
-
42
-
43
折半查找–遞歸法
int BiSearch(int *arr,int left,int right,int k)
{ int mid = left + ((right-left)>>1); while (left<=right)
{ if (arr[mid]==k)
{
return mid;
} else if (arr[mid]>k)
{
return BiSearch(arr,left,mid-1,k);
} else if (arr[mid]<k)
{
return BiSearch(arr,mid+1,right,k);
}
}
return -1;
} int main ()
{ int arr[]={1,2,3,4,5,6,7,8,9,10}; int left = 0; int len = sizeof(arr)/sizeof(arr[0]); int right = len -1;
printf("%d\n",BiSearch(arr,left,right,1));
printf("%d\n",BiSearch(arr,left,right,2));
printf("%d\n",BiSearch(arr,left,right,3));
printf("%d\n",BiSearch(arr,left,right,4));
printf("%d\n",BiSearch(arr,left,right,5));
printf("%d\n",BiSearch(arr,left,right,6));
printf("%d\n",BiSearch(arr,left,right,7));
printf("%d\n",BiSearch(arr,left,right,8));
printf("%d\n",BiSearch(arr,left,right,9));
printf("%d\n",BiSearch(arr,left,right,10));
printf("%d\n",BiSearch(arr,left,right,0));
return 0;
}
以上分別用遞歸和非遞歸進(jìn)行了二分查找，當(dāng)數(shù)組長(zhǎng)度為N時(shí) 非遞歸的時(shí)間復(fù)雜度為O(log N)，空間復(fù)雜度為O(1);遞歸的時(shí)間復(fù)雜度和空間復(fù)雜度均為O(log N)
-
1
-
2
-
3
-
4
-
5
-
6
-
7
-
8
-
9
-
10
-
11
-
12
-
13
-
14
-
15
-
16
-
17
-
18
-
19
-
20
-
21
-
22
-
23
-
24
-
25
-
26
-
27
-
28
-
29
-
30
-
31
-
32
-
33
-
34
-
35
-
36
-
37
-
38
-
39
-
40
-
41
-
42
-
43
-
44
再來(lái)幾個(gè)代碼：
斐波拉契數(shù)——遞歸法
long long fib(int n)
{ if (n<3) return 1; else return ((fib(n-1)+fib(n-2)));
}
斐波拉契數(shù)——迭代法
int main ()
{ int n = 0; long long a = 1; long long b = 1; scanf("%d",&n); if (n<3)
{
b=1;
} else while (n>2)
{
b=a+b;
a=b-a;
n--;
} printf("%lld\n",b); return 0;
-
1
-
2
-
3
-
4
-
5
-
6
-
7
-
8
-
9
-
10
-
11
-
12
-
13
-
14
-
15
-
16
-
17
-
18
-
19
四、簡(jiǎn)單總結(jié)一下：當(dāng)我們?cè)诳吹侥硞€(gè)程序時(shí)有時(shí)候我們無(wú)法進(jìn)行實(shí)際測(cè)試，我們需要用時(shí)間復(fù)雜度和空間復(fù)雜度來(lái)衡量算法的優(yōu)劣性。
本站文章版權(quán)歸原作者及原出處所有 。內(nèi)容為作者個(gè)人觀點(diǎn)， 并不代表本站贊同其觀點(diǎn)和對(duì)其真實(shí)性負(fù)責(zé)，本站只提供參考并不構(gòu)成任何投資及應(yīng)用建議。本站是一個(gè)個(gè)人學(xué)習(xí)交流的平臺(tái)，網(wǎng)站上部分文章為轉(zhuǎn)載，并不用于任何商業(yè)目的，我們已經(jīng)盡可能的對(duì)作者和來(lái)源進(jìn)行了通告，但是能力有限或疏忽，造成漏登，請(qǐng)及時(shí)聯(lián)系我們，我們將根據(jù)著作權(quán)人的要求，立即更正或者刪除有關(guān)內(nèi)容。本站擁有對(duì)此聲明的最終解釋權(quán)。
