几分钟时间让你彻底学会算法在编写成可执行程序的时候，main函数使用这个算法，需要调用一定的空间，消耗一定的时间算法的效率就是通过空间和时间这两个维度来评判的时间复杂度：衡量一个算法的运行速度空间复杂度：衡量一个算法运行需。
算法在编写成可执行程序的时候，main函数使用这个算法，需要调用一定的空间，消耗一定的时间。算法的效率就是通过空间和时间这两个维度来评判的
时间复杂度：衡量一个算法的运行速度
空间复杂度：衡量一个算法运行需要开辟的额外空间
那么我们今天先来看看时间复杂度！
时间复杂度算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。算法中基本操作的执行次数，为算法的时间复杂度
时间复杂度是一个近似值，并不是实际运行的时间
实际上代码的运行时间，和机器的内存、cpu性能和平台都有关系，同一个代码在不同的机器上运行时间都不一样，如果只以纯粹的时间来考核，很难分析
找到某条基本语句与问题规模N之间的数学表达式，就算出了该算法的时间复杂度
void Test(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;}return;}
请问这个代码中，count语句执行了几次？
F ( N ) = N 22 ∗ N10 F(N)=N^2 2*N 10 F(N)=N2 2∗N 10
N = 10 F(N) = 130
N = 100 F(N) = 10210
N = 1000 F(N) = 1002010
你可能会简单地认为，F(N)的结果就是我们的时间复杂度。其实并不然，我们并不需要一个精确的运行次数，只需要知道程序运行次数的量级就行了
这里我们使用大O渐进表示法来表示时间复杂度（空间复杂度同理）
2.1大O的渐进表示法大O符号（Big O notation）：是用于描述函数渐进行为的数学符号
推导大O阶方法：
（1）用常数1取代运行时间中的所有加法常数。
（2）在修改后的运行次数函数中，只保留最高阶项。
（3）如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶
使用这种方法后，test1函数的时间复杂度为
O ( N 2 ) O(N^2) O(N2)
对于test1函数，在计算的时候，我们省略了最后的 10，保留了最高阶数N2，即得出了它的时间复杂度
如果最高阶数前面有系数，如2N，系数也将被省略
因为当N的数值很大的时候，后面的那些值对我们总运行次数的影响已经非常小了。大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数
2.2多种情况取最坏一些算法的时间复杂度会有最好、最坏和平均的情况
最好情况：任意输入规模的最小运行次数(下界)
平均情况：期望的运行次数
最坏情况：任意输入规模的最大运行次数(上界)
举个例子，当我们编写一个在数组中查找数值的算法时，它可能会出现这几种情况：
最好情况：1次就找到
平均情况：N/2次
最坏情况：N次
在实际中的一般情况，我们关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)
2.3常见时间复杂度的计算NO.1
void Func1(int N){int count = 0;for (int k = 0; k < 2 * N ;k){count;}int M = 10;while (M--){count;}printf("%d\n", count);}这里出现了两个循环，分别是2N次和10次。前面提到了大O渐进法只保留最高阶数并省略系数，所以它的时间复杂度是O(N)
NO.2
void Func2(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);}这里出现了次数为N和M的两层循环：
当M和N差不多大的时候，时间复杂度可以理解为O(M)或O(N)
当M远远大于N时，时间复杂度为O(M)
一般情况取O(M N)
NO.3 常数阶
void Func3(int N){int count = 0;for (int k = 0; k < 100;k){count;}printf("%d\n", count);}这里我们得知了具体的循环次数为100，是一常数，时间复杂度为O(1)，代表常数阶
只要循环次数已知，为一常数且和所传参数无关，其时间复杂度即为O(1)
NO.4 strchr
//计算strchr的时间复杂度const char * strchr ( const char * str, int character );看到这道题的时候，你可能会一愣，strchr是什么？
可这里面没有strchr，但有strstr
strstr函数的作用：在字符串1中寻找是否有字符串2
其中第二个str代表的是string字符串，那我们是不是可以猜想，chr代表的是char字符，其作用是在一个字符串中查找是否有一个字符呢？
当然，光是猜想肯定是不够的，我们还需要求证一下
打开 cplusplus网站，搜索strchr，即可转到函数定义
可以看到，该函数的作用是定位字符串中第一次出现该字符的位置，返回值是一个pointer指针
和我们猜想的一样，它的作用就是在字符串中查找一个字符，并返回它第一次出现的位置的地址。
这样一来，strchr函数的时间复杂度就很清楚了，就是遍历字符串所需要的次数，O(N)
NO.5 冒泡排序
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;}} 冒泡排序是一个非常经典的代码，其思路就是遍历整个数组，如果待排序数字大于它的下一位，则交换这两个数字
N个数字的数组需要N-1次排序才能完成
每一次排序都需要遍历一次数组
这样算来，冒泡排序的循环次数就是两个N，即为O(N2)
能否通过循环层级判断？
细心的你可能会发现，上述代码中出现了两层循环，那是不是可以通过循环层级来判断时间复杂度呢？
并不能！
for(int i=0;i<n;i){for(int j=0;j<3;j)printf("hehe\n");}如果是上述这种两次循环的情况，会打印3n次呵呵，其时间复杂度是O(N)而不是N2
我们要准确分析算法的思路，并不能简单地通过循环层级来判断时间复杂度
NO.6 二分查找
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);//使用位移操作符来模拟/2，防止begin和end相加后超出int范围if (a[mid] < x)begin = mid 1;else if (a[mid] > x) end = mid;else return mid;}return -1;}二分查找的思路这里不再赘述
假设我们找了x次，每一次查找都会使查找范围减半
N/2/2/2/2 ……
最后我们可以得出2条公式
2 x = N 2^x=N 2x=N
x = l o g 2 N x=log_2N x=log2N
最好情况：O(1)
最坏情况：O(logN)
通过时间复杂度的对比，我们就能看出二分查找的优势在那里了
可以看到，当数据很大的时候，O(logN)的算法执行次数比O(N)少了特别多!!（来自BT-7274的肯定）
NO.7 计算N!
// 计算阶乘递归Fac的时间复杂度？long long Fac(size_t N){if(0 == N)return 1;return Fac(N-1)*N;}对于这个阶乘的递归函数而言，每次函数调用是O(1)，时间复杂度主要看递归次数
对于数字N而言，递归需要N次，时间复杂度是O(N)
递归算法时间复杂度计算
如果每次函数调用是O(1)，看递归次数
每次函数调用不是O(1)，那么就看他递归调用中次数的累加
NO.8 斐波那契数列
// 计算斐波那契递归Fib的时间复杂度？long long Fib(size_t N){if(N < 3)return 1;return Fib(N-1)Fib(N-2);}每次递归，次数都会增加，总的来说是以2^x的量级增加的（x代表行数）
1248… …2 X − 2 1 2 4 8 …… 2^{X-2} 1 2 4 8 …… 2X−2
这里一共有x-1项，用等比数列的求和公式得出，结果为2x-1
所以最后得出的时间复杂度为O(2N)
需要注意的是，当递归调用到底部时，有一些调用会较早退出，这部分位于金字塔的右下角
由于时间复杂度只是一个估算值，这一部分缺失的调用次数对总运行次数的影响不大，故忽略掉
NO.9
void fun(int n) {int i=l;while(i<=n)i=i*2;}此函数有一个循环，但是循环没有被执行n次，i每次都是2倍进行递增，所以循环只会被执行log2n次
NO.10
给定一个整数sum，从有N个有序元素的数组中寻找元素a，b，使得a b的结果最接近sum，最快的平均时间复杂度是？
A. O(n)//√B. O(n^2)C. O(nlogn)D. O(logn)数组元素有序，所以a,b两个数可以分别从开始和结尾处开始搜，根据首尾元素的和是否大于sum,决定搜索的移动，整个数组被搜索一遍，就可以得到结果，所以最好时间复杂度为n
-----------------------------------
51CTO丨作者：慕雪年华
为了帮助大家，轻松，高效学习C语言/C,给大家分享我收集的资源，从最零基础开始的,帮助大家在学习C语言的道路上披荆斩棘！
编程学习书籍分享：
编程学习视频分享：
整理分享（多年学习的源码、项目实战视频、项目笔记，基础入门教程）最重要的是你可以在群里面交流提问编程问题哦！
对于C/C感兴趣可以关注小编在后台私信我：【编程交流】一起来学习哦！可以领取一些C/C的项目学习视频资料哦！已经设置好了关键词自动回复，自动领取就好了！
,
