本文目录:
1.时间复杂度
1.1时间复杂度的概念
时间复杂度的定义:在计算机科学中,算法的时间复杂度是一个函数,它定量描述了该算法的运行时间。一
个算法执行所耗费的时间,从理论上说,是不能算出来的,只有你把你的程序放在机器上跑起来,才能知
道。但是我们需要每个算法都上机测试吗?是可以都上机测试,但是这很麻烦,所以才有了时间复杂度这个
分析方式。一个算法所花费的时间与其中语句的执行次数成正比例,算法中的基本操作的执行次数,为算法
的时间复杂度。
简单点来说,时间复杂度其实是程序的运算次数,那我们来看看下面这些程序的时间复杂度
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);
}
我们可以通过运算的次数算出这个程序的运算次数:
2.2 大O的渐进表示法
大O符号(Big O notation):是用于描述函数渐进行为的数学符号。
推导大O阶方法:
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中,只保留最高阶项。
3、如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大O阶。
也就是说我们只看影响最大的那个项,本质上是判断它是属于哪个量级的,通过这个方法我们可以判断Func1(上面的代码)时间复杂度:
我们再来练习几个:
// 计算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);
}
F(N) = 2^n + 10 ==> O(N)
当n趋近于无穷大时,2的n次方和5的n次方已经无差异了,所以都可以看成O(N)
// 计算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);
}
O(M+N)
这里如果M远大于N则是O(M),反之则为O(N),而这里就可以看出时间复杂度实际上计算的是最坏的条件
// 计算Func4的时间复杂度?
void Func4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++ k)
{
++count;
}
printf("%d\n", count);
}
O(1)
2.时间复杂度的相关练习题
2.1消失的数字OJ链接
这道题上就有时间复杂度的限制了
这里提供三个思路:
思路一:先排序,在查找
查找:我们通过计算最坏的结果,进行全部遍历的复杂度是: O(N)
排序:1.冒泡排序
int main() {
int arr[10] = { 9,8,7,6,5,4,3,2,1,0 };
int sz = sizeof(arr) / sizeof(arr[0]);
for (int i = 0; i < sz - 1; i++)
{
for (int j = 0; j < sz - 1 - i; j++ )
{
int tmp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = tmp;
}
}
for (int i = 0; i < sz; i++)
{
printf("%d ", arr[i]);
}
return 0;
}
最坏的结果是:所有的数据全部反过来次数为 N-1+N-2+…+2+1
所以F(N)=N*(N-1)/2 ==> O(N^2)
那么这个排序就不行
2.qsort排序
这个排序为快排,它的复杂度我们后面计算,这里了解一下:O(N*logN)
那么我们第一个思路就全都行不通
思路二:先求和然后依次减去数组中的值,剩下的就是消失的数字
这种方法最坏的结果也就是两次遍历也是O(N)
写成代码:
int missingNumber(int* nums, int numsSize) {
int N = numsSize;
int ret = N * (N + 1) / 2;
for (int i = 0; i < numsSize; i++) {
ret -= nums[i];
}
return ret;
}
思路三:异或
原理:相同的值异或就是0;0和任何数异或就是任何数
这里的时间复杂度也是O(N)
int missingNumber(int* nums, int numsSize) {
int N = numsSize;
int x = 0;
for (int i = 0; i < numsSize; i++) {
x ^= nums[i];
}
for (int i = 0; i < N + 1; i++) {
x ^= i;
}
return x;
}
2.2 旋转数组OJ链接
这个题先提供两种解法,后面的解法要到空间复杂度的时候再提出
思路一:直接进行移动
移动2k次其实就是移动k次,所以我们就应该先看看真正移动了多少次
void rotate(int* nums, int numsSize, int k) {
k %= numsSize;
while (k--) {
int tmp = nums[numsSize - 1];
for (int i = numsSize - 2; i >= 0; i--) {
nums[i + 1] = nums[i];
}
nums[0] = tmp;
}
}
但是这里的时间复杂度太大,导致无法通过 O(K*N)
思路二:将前n-k个数逆置,再将后k个数逆置,让后整体逆置
将前n-k个数逆置,再将后k个数逆置,让后整体逆置就会的到结果数组
void exchange(int* nums, int left, int right) {
while (left < right) {
int tmp = nums[left];
nums[left] = nums[right];
nums[right] = tmp;
left++;
right--;
}
}
void rotate(int* nums, int numsSize, int k) {
k %= numsSize;
exchange(nums, 0, numsSize - 1 - k);
exchange(nums, numsSize - k, numsSize - 1);
exchange(nums, 0, numsSize - 1);
}
传参时要注意区分逆置的范围
这样通过一个循环就可以搞定这道题了,那么时间复杂度相较于上一个就少得多