时间复杂度和空间复杂度的简单讲解
2018-09-11 本文已影响0人
付存
一个算法的优劣主要从算法的执行时间和所需要占用的存储空间两个方面衡量。
文章最后，举例使用二分查找和斐波那契的递归和迭代方法，分别说明时间和空间复杂度。
时间复杂度：
首先要说的是，时间复杂度的计算并不是计算程序具体运行的时间，而是算法执行语句的次数。 当我们面前有多个算法时，我们可以通过计算时间复杂度，判断出哪一个算法在具体执行时花费时间最多和最少。常见的时间复杂度有：
常数阶O(1),对数阶O(log2 n),线性阶O(n),线性对数阶O(n log2 n),平方阶O(n^2)，立方阶O(n^3)k次方阶O(n^K),指数阶O(2^n)。随着n的不断增大，时间复杂度不断增大，算法花费时间越多。计算方法 ①选取相对增长最高的项 ②最高项系数是都化为1 ③若是常数的话用O（1）表示 如f（n）=2*n^3+2n+100则O（n）=n^3。通常我们计算时间复杂度都是计算最坏情况
时间复杂度的计算：
（1）如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。int x=1;
while (x <10) {
x++;
}该算法执行次数是10，是一个常数，用时间复杂度表示是O(1)。
（2）当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
;
}
}该算法for循环，最外层循环每执行一次，内层循环都要执行n次，执行次数是根据n所决定的，时间复杂度是O（n^2）。
（3）循环不仅与n有关，还与执行循环所满足的判断条件有关。
int i=0;
while (i < n && arr[i]!=1)
{
i++;
}在此循环，如果arr[i]不等于1的话，时间复杂度是O（n）。如果arr[i]等于1的话，则循环不能执行，时间复杂度是0。
空间复杂度
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。计算方法：
①忽略常数，用O(1)表示
②递归算法的空间复杂度=递归深度N*每次递归所要的辅助空间
③对于单线程来说，递归有运行时堆栈，求的是递归最深的那一次压栈所耗费的空间的个数，因为递归最深的那一次所耗费的空间足以容纳它所有递归过程。
如：
int a;
int b;
int c;
printf("%d %d %d \n",a,b,c);它的空间复杂度O（n）=O（1）；
int fun(int n,)
{
int k=10;
if（n==k)
return n;
else
return fun(++n);
}递归实现，调用fun函数，每次都创建1个变量k。调用n次，空间复杂度O（n*1）=O（n)。
举例说明
1：实现二分查找算法的递归及非递归。（分析时间复杂度及空间复杂度）
迭代算法
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<string.h>
#include<assert.h>
int BinarySearch(int arr[], int len, int num)
{
assert(arr);
int left = 0;
int right = len - 1;
int mid;
while (left <= right)
{
mid = left + (right - left) / 2;
if (num > arr[mid])
{
left = mid + 1;
}
else if (num < arr[mid])
{
right = mid - 1;
}
else
{
return mid;
}
}
return -1;
}
int main()
{
int arr[] = { 1,2,3,4,5,6,7,8,9 };
int length = sizeof(arr) / sizeof(arr[0]);
int aim = 9;
int result;
result = BinarySearch(arr, length, aim);
if (result == -1)
{
printf("Can't find %d\n", aim);
}
else
{
printf("%d at %d postion\n", aim,result + 1);
}
return 0;
}二分查找时，每次都在原有查找内容进行二分，所以时间复杂度为O（log2 n）
因为变量值创建一次，所以空间复杂度为O（1）
递归算法
int BinarySearchRecursion(int arr[5], int lef, int rig,int aim)
{
int mid = lef + (rig - lef) / 2;
if (lef <= rig)
{
if (aim < arr[mid])
{
rig = mid - 1;
BinarySearchRecursion(arr, lef, rig, aim);
}
else if (arr[mid] < aim)
{
lef = mid + 1;
BinarySearchRecursion(arr, lef, rig, aim);
}
else if (aim == arr[mid])
{
return mid;
}
}
else
return -1;
}
int main()
{
int arr[] = { 1,2,3,5,6, };
int sz = sizeof(arr)/sizeof(arr[0]);
int result;
result = BinarySearchRecursion(arr, 0, sz - 1, 4);
if (-1 == result)
{
printf("Can't find it.\n");
}
else
printf("Aim at %d location\n", result+1);
}时间复杂度为O（log2 n）
每进行一次递归都会创建变量，所以空间复杂度为O（log2 n）
2：实现斐波那契数列的递归及非递归。（分析时间复杂度及空间复杂度）
迭代算法
int FeiBoNaCciInteration(int a,int b,int num)
{
int c;
if (num <= 0)
return -1;
else if (num == 1)
return a;
else if (num == 2)
return b;
else
{
while (num - 2)
{
c = a + b;
a = b;
b = c;
num--;
}
return c;
}
}
int main()
{
int n;
int result;
printf("Input n\n");
scanf("%d", &n);
result = FeiBoNaCciInteration(2, 3, n);//可自定义输入第一个数和第二个数
if (result == -1)
{
printf("Input Error!\n");
}
else
{
printf("n is %d\n", result);
}
return 0;
}时间复杂度O（n)
空间复杂度为O（1）
递归算法
int FeiBoNaCciRecursion(int num)
{
if (num < 0)
return -1;
if (num <= 2 && num > 0)
return 1;
else
return FeiBoNaCciRecursion(num - 1) + FeiBoNaCciRecursion(num - 2);
}
int main()
{
int n;
int result;
printf("Input n\n");
scanf("%d", &n);
result = FeiBoNaCciRecursion(n);
if (result == -1)
printf("Input Error!\n");
else
printf("Result is %d\n", result);
return 0;
}时间复杂度为O（2^n）
空间复杂度为O（n）
