目录
前言
一、时间复杂度
二、大O表示法
三，实例介绍
例1：O(N^2)
例2：O（1）
例3：O(M +N)
（重点）例4：O（N）
例5：冒泡排序（ O(N^2) )
例6：二分法查找(O（log2N）)
例7：
(1)递归法（阶乘）O(N) | O(1)
（2）递归法（斐波那契数列)（ O(2^N）)
总结
前言
本文介绍数据结构的入门——时间复杂度。将会对时间复杂度进行剖析，通过例题讲解时间复杂度的应用范围和注意事项。
一、时间复杂度
概念：算法的时间复杂度是一个函数：（是数学含义上的函数）数据里面带未知数的函数式。
含义：算法在机器中运行所消耗的时间。
实际意义：算法中基本操作的执行次数。
作用和理解：降低占用内存和减少运行时间，提高效率。
好的算法相当于拿着筷子吃饭，差的算法相当于拿着竹竿吃饭，又长又麻烦。
二、大O表示法
大O符号（Big O notation）:用于描述函数渐进行为的数学符号（描述时间复杂度）
推导大O阶方法：
1，用常数1取代运行次数中的所有加法常数；
2，在修改后的运行次数函数中，只保留最高阶项；
3，如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶；
含义：（保留最高阶的未知数，不保留常系数）。
三，实例介绍
例1：O(N^2)
找到某条基本语句与问题规模N之间的数学表达式，就是算出了算法的时间复杂度。
代码如下：
//请计算一下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);
Func1 执行的基本操作次数：F（N）= N^2+2*N+10 O（N^2）
- N =10 F(N) = 130
- N =100 F(N) =10210
- N = 1000 F(N) =1002010
- 随着N的变大，后两项的结果影响逐渐变小
- 当N无限大的时候，后两项对结果的影响可以忽略不计。
- 所以时间复杂度为O(N^2)。
例2：O（1）
代码如下：
void Func2(int N) {int count =0;for(int i =0;i<100；++i){ ++count;}如果只是循环次数只是常数项的话者就直接是O（1）
例3：O(M +N)
代码如下：
void Func1(int N， int M) {int count =0;for(int i =0;i<N；++i){++count;}for(int k = 0; k < M; ++k){ ++count;}printf("%d\n",count);虽然是不同的未知数，但是时间复杂度O只看阶数：所以为O（M）或O（N）
（重点）例4：O（N）
计算strchr的时间复杂度
const char* strchr(const char *str,int character);
whlie（*str）
{if（*str==chaeacter）return str；else++str;
}
return NULL;
此类时间复杂度是通过输入进去的数组的元素个数确定。
- 最好可以为1
- 最坏可以为N
- 但是时间复杂度一般取最坏的情况，所以此题的搜索数组数据的时间复杂度为O（N）
- 有些算法的时间复杂度存在最好，平均，最坏情况：
- 最坏情况：输入任意规模的最大运行次数（次数上限）
- 平均情况：输入任意期望的运行次数
- 最好情况：输入任意规模的最小运行次数（次数下限）
例5：冒泡排序（ O(N^2) )
int Fib(int *a, int size_a) {for (int i =0;i<size_a -1;i++){for (int j = 0; j< size_a -1 -i;j++){int temp;if( a[j] < a[j+1] ){temp = a[j];a[j] = a[j+1]a[j+1] = temp;}}}}
例6：二分法查找(O（log2N）)
我们要准确分析算法时间的复杂度，一定要去看思想，不能只去看程序是几层循环。
int BinarySearch（int*a, int n, int x） {assert(a); //排序int begin =0;int end =n;while (begin <end){int mid = begin +((end-begin)>>1);if(a[mid] < x)begin = mid+1;else if(a[mid]> x)end = mid;else return mid;}return -1; }
N（循环次数）X（查找次数）
通常运算级的大小在初始基数特别大的时候比较有优势。
例7：
(1)递归法（阶乘）O(N) | O(1)
时间复杂度计算·
1，每次函数调用为O（1），那么就看他的递归次数
2，每次函数调用不是O（1），那么就看他的递归调用中次数的累加
long long Fac （size_t N）
{if(0 ==N)return 1;return Fac(N-1)*N;
}
（2）递归法（斐波那契数列)（ O(2^N）)
long long Fib(size_t N) {if(N < 3)return 1;return Fib(N-1) +Fib(N-2); }
递归法算斐波那契数列是比较占用内存的一种方法，运行次数随着设定值呈指数性增长。
总结
1.本次讲了时间复杂度的基本认识。
通过对7例不同的时间复杂度的分析，我们可以得出以下结论：
（1）时间复杂度不局限与循环有关，核心是与算法思想有关。
（2）时间复杂度主要取其最坏循环次数。
（3）通过对时间复杂度的认识，能更好的对我们的程序进行优化。
