一、时间复杂度：（注意：不是指程序运行时间）
1定义：一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=Ｏ(f(n)),称Ｏ(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。
2、 计算方法：在计算时间复杂度的时候，先找出算法的基本操作，然后根据相应的各语句确定它的执行次数，再找出 T(n) 的同数量级（它的同数量级有以下：1，log2n，n，n log2n ，n的平方，n的三次方，2的n次方，n!），找出后，f(n) = 该数量级，若 T(n)/f(n) 求极限可得到一常数c，则时间复杂度T(n) = O(f(n))
二、空间复杂度（注意：不是计算空间，而是指对象的个数）
1、空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度，记做S(n)=O(f(n))。比如直接插入排序的时间复杂度是O(n^2),空间复杂度是O(1) 。而一般的递归算法就要有O(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;
}
以上分别用递归和非递归进行了二分查找，当数组长度为N时 非递归的时间复杂度为O(log N)，空间复杂度为O(1);递归的时间复杂度和空间复杂度均为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
再来几个代码：
斐波拉契数——递归法
long long fib(int n)
{ if (n<3) return 1; else return ((fib(n-1)+fib(n-2)));
}
斐波拉契数——迭代法
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
四、简单总结一下：当我们在看到某个程序时有时候我们无法进行实际测试，我们需要用时间复杂度和空间复杂度来衡量算法的优劣性。
本站文章版权归原作者及原出处所有 。内容为作者个人观点， 并不代表本站赞同其观点和对其真实性负责，本站只提供参考并不构成任何投资及应用建议。本站是一个个人学习交流的平台，网站上部分文章为转载，并不用于任何商业目的，我们已经尽可能的对作者和来源进行了通告，但是能力有限或疏忽，造成漏登，请及时联系我们，我们将根据著作权人的要求，立即更正或者删除有关内容。本站拥有对此声明的最终解释权。
