目录
- 算法效率
- 时间复杂度
- 空间复杂度
- 练习
1. 算法效率
1.1 如何衡量一个算法的好坏
比如裴波那切数列:
long long Fib (int N)
{
if (N < 3)
return 1 ;return Fib(N-1) + Fib(N -2) ;
}
它的递归方式很简洁,但一定好吗?怎么衡量算法的好坏?
1.2 算法的复杂度
算法在编写可执行程序后,运行时需要消耗时间资源和空间(内存)资源。因此衡量一个算法的好坏,一般从时间和空间两个维度衡量,即时间复杂度和空间复杂度
时间复杂度主要衡量一个算法的运行快慢
空间复杂度衡量算法运行所需要的额外空间
在计算机发展的早期,存储容量很小,所以对于空间复杂度很在乎,但是经过迅速发展,计算机的存储容量已经达到了很高的程度。所以如今已经不需要再特别关注算法的空间复杂度
2. 时间复杂度
2.1 时间复杂度的概念
时间复杂度的定义: 在计算机科学中,算法的时间复杂度是一个函数(数学),描述了算法的运行时间,一个算法消耗的时间从理论上,是算不出来的,只有在机器上跑起来,才能知道,但每次上机测试很麻烦,所以有了时间复杂度的分析方式,一个算法所花费的时间与其中语句的执行次数成正比例,算法中的基本操作的执行次数,为算法的时间复杂度
找到某条基本语句与问题规模N之间的数学表达式,就是该算法的时间复杂度
//计算一下++count总共执行了多少次
void Func1(int N)
{int count = 0;for (int i = 0; i < N; i++){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);
Func1执行的基本次数:
首先有两个for循环,就是N的平方次,下面的for循环次数是2*N,最后的while循环,次数固定是10
F(N) = N2 + 2 * N + 10
- N = 10 F(N) = 130
- N =100 F(N) = 10210
- N=1000 F(N) = 1002010
- 实际中计算时间复杂度时,并不一定要一定要精确的执行次数,只需要大概执行次数,这个就是大O的渐进表示法
2.2 大O的渐进表示法
大O符号(Big O notation):用来描述函数渐进行为的数学符号
推导大O阶的方法:
- 用常数1取代运行时间中所有加法常数
- 在修改后的运行次数函数中,只保留最高阶
- 如果最高阶项存在且不是1,则去除与这个项目相乘的常数,得到的结果就是大O阶
当影响执行次数的变量特别大时,常数的影响微乎其微,时间复杂度只描述最高阶,同样,数量越大,1次方的影响和二次方比越来越小,常数系数也可以省略
这样,大O表示Func1的时间复杂度:
- N = 10 F(N) = 100
- N = 100 F(N) = 10000
- N = 1000 F(N) = 1000000
大O渐进法去掉了对结果影响不大的项,简明表示出了执行次数
另外有些算法存在三种情况:
最坏情况:任意输入规模的最大运行次数(上界)
平均情况:任意输入规模的期望运行次数
最好情况:任意输入规模的最小运行次数(上界)
例如找一个数据:
最好情况1次就找到,最坏情况N次找到,平均N/2次找到
在实际中一般情况关注的是最坏运行情况,底线思维。所以数组上面找数据的时间复杂度为O(N)
2.3 举例
例1:
// 计算Func2的时间复杂度?
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);
}
实际执行2 * N + 10 次,大O表示为O(N)
例2:
// 计算Func3的时间复杂度?
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);
}
实际执行了M + N次,有两个未知数,所以为O(M + N)
例3:
// 计算Func4的时间复杂度?
void Func4(int N)
{int count = 0;for (int k = 0; k < 100; ++k){++count;}printf("%d\n", count);
}
实际执行100次,时间复杂度O(1),表示常数次
例4:
// 计算strchr的时间复杂度?
const char* strchr(const char* str, int character);
最好情况: 第一次就找到
平均情况: character/2
最坏情况: character次找到或未找到
时间复杂度为O(N)
例5:
// 计算BubbleSort的时间复杂度?
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;}
}
第一次执行end-1次
第二次执行end-2次
。。。
一直到执行1次
这是一个等差数列,求和 N(1 + N ) /2,大O结果为 O(N2)
例6:
// 计算BinarySearch的时间复杂度?
int BinarySearch(int* a, int n, int x)
{assert(a);int begin = 0;int end = n - 1;while (begin < end){int mid = begin + ((end - begin) >> 1);if (a[mid] < x)begin = mid + 1;else if (a[mid] > x)end = mid;elsereturn mid;}return -1;
}
二分查找,每找一次,数据集就会缩小当前的一半
第一次需要找N次
第二次需要找N/2次
第三次需要找N/2/2次
。。。
当数据集只剩1个时,就有了结果
假设找了x次,2x = N ,结果就是log2N
时间复杂度O(logN)
logN是优于N的,和折纸相似,可以将数据集扩大看看两者的差距
当14亿数据集时,二分查找最多只需要31次就可以找到
例7:
// 计算阶乘递归Fac的时间复杂度?
long long Fac(size_t N)
{if (0 == N)return 1;return Fac(N - 1) * N;
}
第一次递归Fac(N-1)
第二次递归Fac(N-2)
。。。
最后到Fac(0)
时间复杂度为O(N)
例8:
// 计算斐波那契递归Fib的时间复杂度?
long long Fib(size_t N)
{if (N < 3)return 1;return Fib(N - 1) + Fib(N - 2);
}
每一次都需要递归两个函数,公式为
F(n) = 20 + 21 + … 2(n-2)
2F(n) = 21 + 22 + … 2(n-2) + 2(n-1)
用错位相减法,可以抵消,得
2^(n-1) - 1
保留最高项,O(2n)
3. 空间复杂度
空间复杂度也是一个数学表达式,是对一个算法运行过程临时占用存储空间大小的量度
空间复杂度不是程序占用了多少bytes的空间,算的是变量的个数,也用大O渐进法表示
注意:函数运行时所需要的栈空间(存储参数、局部变量、寄存器信息等)在编译期间已经确定好了,空间复杂度是函数运行申请的额外空间来确定
例1:
// 计算BubbleSort的空间复杂度?
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;}
}
只有一个变量exchange,所以是O(1)
例2:
// 返回斐波那契数列的前n项
long long* Fibonacci(size_t n)
{if (n == 0)return NULL;long long* fibArray = (long long*)malloc((n + 1) * sizeof(long long));fibArray[0] = 0;fibArray[1] = 1;for (int i = 2; i <= n; ++i){fibArray[i] = fibArray[i - 1] + fibArray[i - 2];}return fibArray;
}
开辟了N+1个longlong,所以复杂度O(N)
例3:
// 计算阶乘递归Fac的空间复杂度?
long long Fac(size_t N)
{if (N == 0)return 1;return Fac(N - 1) * N;
}
每次开辟N个函数空间,每个栈帧使用常数个空间,O(N)
类似的,递归计算裴波那切数列的空间复杂度也是O(N)
因为时间是一去不复返的,空间是可以重复利用的,函数开辟的空间可以重复利用,每次只会执行一个函数
void fun1() {int a = 0;printf("%p\n", &a);
}void fun2() {int b = 0;printf("%p\n", &b);
}
上面代码,执行后地址是一样的,证明两个函数用的同一份空间
4. 常见复杂度对比
5201314 | O(1) | 常数阶 |
3n+4 | O(n) | 线性阶 |
3n2+4n+5 | O(n2) | 平方阶 |
3log(2)n+4 | O(logn) | 对数阶 |
2n+3nlog(2)+14 | O(nlogn) | nlogn阶 |
n3+2n2+4n+6 | O(n3) | 立方阶 |
2n | O(2n) | 指数阶 |
5. 复杂度练习
第一种:
排序后,依次查找,如果下一个数不是上一个数加1,就找到了这个数
时间复杂度最好的情况是O(N*logN)
第二种:
将数组内所有数异或,再异或数组长度内每个数,就可以找到这个数
时间复杂度O(N)
int ary[] = { 9, 6, 4, 2, 3, 5, 7, 0, 1 };
int len = sizeof(ary) / sizeof(ary[0]);
int x = 0;for (int i = 0; i < len; i++)
{x ^= ary[i];
}for (int i = 0; i < len + 1; i++)
{x = x ^ i;
}printf("%d", x);
第三种:
0-N等差数列公式求和,减去数组每个值
时间复杂度O(N)
int x = len * (len + 1) / 2;for (int i = 0; i < len; i++)
{x -= ary[i];
}printf("%d", x);
第一种:
暴力求解,旋转k次
时间复杂度:O(N2)
空间复杂度: O(1)
第二种:
三段逆置
void Reverse(int ary[], int left, int right)
{while (left < right){int temp = ary[left];ary[left] = ary[right];ary[right] = temp;left++;right--;}
}void Rotate(int ary[], int len, int k)
{if (k > len)k %= k;Reverse(ary, 0, len - k - 1);Reverse(ary, len - k, len - 1);Reverse(ary, 0, len - 1);
}int nums[] = { 1, 2, 3, 4, 5, 6, 7 };
int len = 7;
int k = 3;
Rotate(nums, 7, k);
for (int i = 0; i < len; i++)
{printf("%d ",nums[i]);
}
时间复杂度: O(N)
空间复杂度: O(1)
第三种:
空间换时间
轮转3个,先把后面的5,6,7放到新数组里,再把前面的拼上
void Rev(int ary[], int len, int k)
{if (k > len)k %= k;int* p = (int*)malloc(len * sizeof(int));memcpy(p, ary + len - k, sizeof(int) * k);memcpy(p + k, ary, sizeof(int) * (len - k));memcpy(ary, p, sizeof(int) * len);free (p);p = NULL;
}
时间复杂度:O(N)
空间复杂度: O(N)