一、前言
在学习AJAX的同时也会写一些关于数据结构的东西，想要不同于常人，就需要付出更多的努力，任何事情都是需要坚持，加油！
二、穷举法
在学习时间复杂度之前我们先来了解一下什么是穷举
1.单层循环
穷举法：穷举法就是我们通常所说的枚举，就是把所有的情况都遍历一遍。
举个简单的例子：
个元素
，求其中 奇数 有多少个。
判断一个数是不是奇数，只需要求它除上2的余数是0还是1，那么我们是不是需要将这n个元素都判断一次，并对符合条件的情况进行计数
示例代码 如下
int Count(int n,int a[])
{
int count =0;
for(int i=0;i<n;i++)
{
if(a[i]%2==0)
{
count++;
}
}
return count;
}2.双层循环
我们依旧用一个例子来说明
个元素
，求有多少个二元组
，满足
是奇数
。
int CountTwo(int n,int a[])
{
int count =0;
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
if((a[i]+a[j])%2==0)
{
count++;
}
}
}
return count;
}此时我们用了两次循环
3.三层循环
个元素
，求有多少个三元组
，满足
我们直接上示例代码
int CountThree(int n,int a[])
{
int count =0;
for(int i=0;i<n;i++)
{
for(int j=i+1;j<n;j++)
{
for(int k=j+1;k<n;k++)
{
if((a[i]+a[j]+a[k])%2==0)
{
count++;
}
}
}
}
return count;
}我们会发现随着循环嵌套增多，代码运行的次数会越来越多，那么我们消耗的时间也会越来越多
三、时间复杂度
1.时间复杂度的表示法
算法中基本语句的执行次数子啊渐近意义下的阶，称作算法的渐进时间复杂度，简称时间复杂度，通常用O记号表示。（读不懂很正常，下面例子才是重点）
用大写的 O 来体现算法时间复杂度的记法，我们称之为 大 O 记法
（T(n）=O(f(n))
2.时间函数
时间复杂度往往会联系到一个函数，自变量 表示规模，应变量 表示执行时间。
注意：这里的执行时间并不是我们理解的上的秒、分、时，而是执行次数
3.经典函数举例
在上述例1中，也就是单层循环的例题
它的f(n)=n 也就是说它的时间复杂度为O(n)
例2当中，双层循环
f(n)=n(n−1)/2，时间复杂度为O(n*n)
例3中，三层循环
f(n)=n(n−1)(n−2)/6，时间复杂为O(n*n*n)
这时候我们会发现f(n)很复杂，但是O表示的往往比f(n)函数表示的简单，这是为什么呢？
这就是高数里面有一种概念叫“高阶无穷小”
3.高阶无穷小
定义：，则称“
是比
这里我直接用例子来说明，这样比较好懂
也就是说，随着n的增长，n的平方部分会变的越来越大，而n相对于n的平方来说，就“微不足道”了。
也就可以得到以下化简
4.简化系数
我们会发现上述化简的时候我们将1/2给去掉了，这是由于 时间复杂度描述的更多的是一个数量级，所以尽量减少干扰项。对于两个不同的问题，可能执行时间不同，但是我们可以说他们的 时间复杂度 是一样的。
四、常见的时间复杂度
1.常数阶
#include<stdio.h>
int main()
{
int a=1024;
printf("%d",a);
}这个没有循环，是常数时间，表示为O(1)；
2.对数阶
给定 个元素的有序数组
和 整数
，求
在数组中的下标，不存在输出-1
这道题告诉我们这个数组是有序的，从这个有序的数组当中去找整数v，那么我们可以使用二分查找来实现
int bin(int n,int a[],int v)
{
int l=0,r=n-1;
while(l<=r)
{
mid = (l+r)/2;
if(a[mid]==v) return mid;
else if(a[mid]<v)
{
r=mid+1;
}
else
{
l=mid+1;
}
}
return -1;
}这是一个二分查找的实现，时间复杂度为O(log2n)
3.根号阶
给定一个数n，问n是否为一个素数
- 基于素数的概念，我们可以枚举所有
，看能否整除
，一旦能整除，代表找到了一个因子，则不是素数；当所有数枚举完还没找到，它就是素数。
- 但是这样做，显然效率太低，所以我们需要进行一些思考，最后得到以下算法：
int isPr(int n)
{
if(n<=1)
{
return 0;
}
for(int i=2;i<=sqrt(n);i++)
{
if(n%i==0)
{
return 0;
}
}
return 1;
}时间复杂度为
4.线性阶
例一当中的单层循环就是很经典的线性时间
时间复杂度为O(n)
5.线性对数阶
给定 个元素
，求满足
的有序二元组
有多少对
按照递增排序，然后枚举
，并且在
范围内找是否存在
，存在则计数器 + 1，而这个找的过程可以采用二分枚举。所以时间复杂度就是：O(nlog2n)。
6.多项式阶
O(n5)、O(n4)、O(n3)...都是多项式阶
7.指数阶
时间复杂为O(n22n）
8.阶乘阶
给定 个点，并且给出任意两点间的距离，求从
点开始经过所有点回到
的距离最小值
这道题直接暴力枚举所有的情况，可以把这些点当成一个排列，所以排列方案数为n！
时间复杂度为O(n!)