时间和空间复杂度

一.时间复杂度

1.关于定义

衡量一个算法的运行快慢，如今更看重时间复杂度，因为计算机的存储容量已经达到很高啦

算法的时间复杂度是一个函数（数学意义的函数）来定量描述算法的运行时间

从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个 分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。

// 请计算一下Func1中++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);}

在计算复杂度时，我们引入大O渐进表示法：

1.常数1取代运行时间中的所有加法常数（O(1)表示的不是运行一次而代表运行常数次）

2.修改后的运行函数中，只保留最高阶项

3.最高项存在且系数不为1，则去除系数

所以上述函数的时间复杂度是O(n^2)

1.2一些原理

为什么只保留最高阶项呢？从极限的角度思考，比如x^2的无穷必然大于x的无穷（可以联想微积分的抓大头）；但是为什么从极限角度考虑呢，小于一的时候，x>x^2啊？

这涉及到一些硬件知识，比如51单片机，它使用比较低级的晶振来计时从而驱动单片机运行代码。这样的晶振，一般都是12MHz，什么概念，就是你的电脑即使再差劲一秒钟运行的代码次数也是上亿次，数学上有差异的函数放到电脑上运行就会发现它的运行时间实在是太短了，所有的代码都是看不出来优劣的，性能是一样的（不信的话可以自己运行一下加法函数，加1000000回，再使用time.h的clock()函数，你会发现是0ms的运行时间）（不是说不用时间，而是说这个运行时间不到一毫秒）

在趋近于无穷的时候，最高项前面的常数就对于这个算法影响不大了

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);}

// 计算Func4的时间复杂度？
void Func4(int N){int count = 0;for (int k = 0; k < 100; ++ k){++count;}printf("%d\n", count);}

// 计算strchr的时间复杂度？
const char * strchr ( const char * str, int character );

// 计算BinarySearch的时间复杂度？
int BinarySearch(int* a, int n, int x){assert(a);int begin = 0;int end = n-1;// [begin, end]：begin和end是左闭右闭区间，因此有=号while (begin <= end){int mid = begin + ((end-begin)>>1);if (a[mid] < x)begin = mid+1;else if (a[mid] > x)end = mid-1;elsereturn mid;}return -1;}

// 计算斐波那契递归Fib的时间复杂度？
long long Fib(size_t N){if(N < 3)return 1;return Fib(N-1) + Fib(N-2);}

// 计算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;}}

1.O(m+n)

这个就要看具体m n的大小关系了，谁大就是谁

2.O(1)

因为是常数次呀

3.O(n)

说明：该函数是查找字符串中某个字符是否存在的

这个有最好，最差和一般情况；最好：1次，最差：n次，一般：(1+2+3+...+n)/n次

有多种情况时，我们看最差情况，就知道是O(n)

或者要用定义来看，看一般次数，会发现用规则后也是一样的结果

4.O(logn)

二分查找算法：针对已经有序的数组

最坏情况：区间只剩一个数或者找不到
查找了多少次就除了多少个2
假设查找了x次
2^x=N;所以复杂度为o(logN)

log2N可以直接写成logN；
其他底数是不能省略的！（虽然说其他底数是不常见的）

这个算法效率极高，举个例子，他用31次就能从排列好的身份证号中查找出14亿人中的你

但是不常用，为什么呢？

首先它需要排序，其次最致命的他需要数组结构，而数组结构是不方便插入删除的（链表也是不行的，因为他无法直接随机读取）

5.O(2^n)

给大家看个图

它是以2的指数级形式增长，具体而言就是(2^(n-2))+2这么多次（自己用等差数列推到一下就出来了）但是其实你知道是2的指数级形式增长就可以直接出结论了

6.O(n^2)

外面的循环会走n次，但是第n次end==1里面不会再进去了！！！相当于还是1，2，3，...n-1的等差数列求和！

二.空间复杂度

1.定义

空间复杂度也是一个数学表达式，是对一个算法在运行过程中临时占用存储空间大小的量度 。

空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。

空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。

注意：函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了（在之前的讲解预处理的文章有讲解），因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。

2.算算空间复杂度

// 计算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;}}

// 计算Fibonacci的空间复杂度？
// 返回斐波那契数列的前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;

 // 计算斐波那契递归Fib的空间复杂度？
long long Fib(size_t N){if(N < 3)return 1;return Fib(N-1) + Fib(N-2);}

1.O(1)

原地操作必然是不用额外空间的

2.O(n)

开辟了一个长度为n的数组（注意注意下面的分析！）

3.O(2^n)?  其实是O(n)!

递归函数调用会有栈帧，直到这个值被返回，栈帧才会销毁；如图，红色箭头代表调用、创建栈帧；蓝色代表结束调用，栈帧释放；注意释放后的栈帧是可以重复使用的

1=8是最长的一趟线，一共有5个数，四个栈帧；我们可以推理出来，第n个斐波那契数只需要n-1个栈帧（因为最左下角的f(1)f(2)是已知的，使用完f(2)栈帧释放再放进去f(1)调用的栈帧

这里有个很鸡肋的东西：比如f(3)，我们会发现相同的数据居然算了这么多次！这导致不断地重复计算；不像上面的题目，已经算出的值被保存了，递归也是使用的数组的值计算出来就可以直接用了！！所以他的时间复杂度会是O(n)而不是O(2^n)；

三.相关习题

面试题 17.04. 消失的数字 - 力扣（LeetCode）

    //思路1：先排序再依次查找；如果下一个不等于前一个+1，下一个就是缺失的

    //卡死了：因为排序就需要选择算法快速排序都是O(logn*n)了；再加上遍历的时间复杂度已经                         O(n)了，这个方法失败

    //思路2：求和再依次减去数组中的值

                   只需要遍历一遍数组，求和可以直接用公式；或者再遍历一遍也行啊，这两个的时间                       复杂度都是O(n)

    //思路3：思路2存在溢出风险：异或

                  0^任何数=任何数

                  任何数^自己=0

                  使用这个性质可以解决问题

    //相同为0相异为1

    // int ret=(numsSize+1)*numsSize/2;// for(int i=0;i<numsSize;i++)// {//     ret-=nums[i];// }// return ret;int n=numsSize;int x=0;for(int i=0;i<numsSize;i++){x^=nums[i];}for(int j=0;j<=numsSize;j++){x^=j;}return x;

189. 轮转数组 - 力扣（LeetCode）

方法一：直接往后挪

// //直接往后挪的时间复杂度o(k*N)?

    // //难道k真的是未知的，不能确定的，留在这里吗

    // //其实k是从k%=n的

    // //最坏情况下是o(n^2)(n-1次)；最好是o(1)(1次)；

    // //but这个算法过不了

    // 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;

    // }

    // //乐。

结论是时间复杂度太高了，给了一个巨大数组，超时了

思路二：

先整体逆置；然后把前面的K个再逆置；最后的也逆置

void Swap(int left,int right,int* arr)
{while(left<right){int tmp = arr[left];arr[left]=arr[right];arr[right]=tmp;left++;right--;}
}void rotate(int* nums, int numsSize, int k) {//思路二：三段逆置k%=numsSize;int front=numsSize-k;int back=k;Swap(0,numsSize-1,nums);Swap(0,back-1,nums);Swap(back,numsSize-1,nums);//思路三：另开数组，直接粘贴，再反向粘回去
}

思路三：新开数组，然后把最后K个粘到前面，最后把剩下的依次粘到后面

总结：在做题时，我们先想思路，判断其复杂度然后在写代码

以上就是全部内容，希望大家批评指正！