好的，同志们，终于又开始写博客了，距上一个博客已经长达一个半月的时间了，也许是因为期末考试，也许是因为复习，但是，从今天就不提出那些理由了，我们现在开始来了解前辈们口中的所谓的数据结构。
1.什么是数据结构？
数据结构是计算机存储，组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。
2.什么是算法？
算法：就是定义良好的计算过程，他取一个或一组的值为输入，并产生一个或一组值作为输出。简单来说算法就是一系列的计算步骤，用来将输入数据转化成输出结果。
3.如何学好数据结构和算法
3.1死磕代码
3.2注意画图和思考
好的，接下来我们进行 今天的十分重要的内容。
算法的时间复杂度
【本节目标】
1.算法效率
2.时间复杂度
3. 常见时间复杂度以及复杂度oj练习
开始
1.算法效率
1.1如何衡量一个算法的好坏，这是个问题。
如何衡量一个算法的好坏呢？比如对于一下斐波那契额数列：
long long Fib(intN)
{
if(N<=3)
return 1;
return Fib(N-1) + Fib(N-2);
}
斐波那契数列的递归实现方式非常简洁，但是间接一定好吗？那该如何衡量其好与坏呢？
1.2算法的复杂度
算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏，一般 是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。
时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计 算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。让我们有请今晚的主角
时间复杂度
2.时间复杂度
2.1时间复杂度的概念
时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来才能知道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个 分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法 的时间复杂度。
即：找到某条基本语句与问题规模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 j = 0; k < 2 * N ;++k）
{
++count;
}
int M = 10;
while(M--)
{
++count;
}
printf("%d
",count);
}
执行次数为 F(N)=N^2+2*N+10
而它的时间复杂度为O(N^2) 这是为什么呢？
实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大O的渐进表示法。
2.2大O的渐进表示法
大O符号：是用来描述函数渐进行为的数学符号。
推导大O阶方法：
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中，只保留最高阶项。
3、如果最高阶项存在且不是1，则去除这个项目相乘的常数。得到的结果就是大O阶。
使用大O阶渐进表示法以后，Func1的时间复杂度为：O(N^2)
通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数。
另外有些算法的时间复杂度存在最好、平均和最坏情况：
最坏情况：任意输入规模的最大运行次数(上界)
平均情况：任意输入规模的期望运行次数
最好情况：任意输入规模的最小运行次数(下界)
例如：在一个长度为N数组中搜索一个数据x
最好情况：1次找到
最坏情况：N次找到
平均情况：N/2次找到
在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)
2.3常见时间复杂度计算举例
实例1：
void Fun2(int N)
{
int count = 0;
for (int K = 0; K < 2 * N; ++K)
{
++count;
}
int M = 10;
while (M--)
{
++count;
}
printf("%d
", count);
}
其中count的运行次数为 2*N+10,按照我们的大O渐进表示法它的时间复杂度为O(N)
实例2：
void Fun3(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
", count);
}
这个代码中count的运行次数为M+N 它的时间复杂度为 O(M+N)
如果M和N一样大则时间复杂度为O(N)或O(M)
如果M>>N 则时间复杂度为O(M)
如果N>>M 则时间复杂度为O(N)
实例3：
void Fun4(int N)
{
int count = 0;
for (int k = 0; k < 100; ++k)
{
count++;
}
printf("%d
", count);
}
这个代码中 count运行的次数是100 则它的时间复杂度为O(1)用常数1取代运行时间中的所有加法常数。
实例4：
// 计算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;
}
}
这是一个冒泡排序的代码，由图分析可知，要把最大的数浮到最右边，需要进行n-1次交换，依次类推，是个等差数列，求和为 （n-1）*n/2 它的时间复杂度为O(N*2);
实例5：
// 计算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;
else
return mid;
}
return -1;
}
二分查找，即从一组有序数组中找到一个数，比如有n个数，则判断要查找的数是否大于等于小于n/2，如果大于则在（n/2+1，n）中查找，如果小于n/2则在小于（n/2-1）查找，以此类推找到为止，或者找不到。
二分查找中最好的情况是一次查到，最坏的情况是查找区间缩放只剩一个值时就是最坏。
最坏的情况下查找了多少次？ n/2 n/4 n/8 n/16... 即 y=log n 这是有同学肯定会有疑问，怎么这样写，因为对数文本中不好写，支持一些展示公式编辑器才方便，时间复杂度简写成logN，只有log2N才可以简写成logN，其他的都得写出来，有些资料会把logN写成lnN这样是不严谨的。一定不要这么写。
为什么用二分查找呢，如果把14亿身份证号放在数组中排序，然后用二分查找插一个人，最坏只需要查31次，而直接暴力查找呢，最坏要查14亿次。虽然二分查找速度快，但是缺点也很明显，需要提前排序。
实例6：
// 计算阶乘递归Fac的时间复杂度？
long long Fac(size_t N)
{
if (0 == N)
return 1;
return Fac(N - 1) * N;
}
为什么这个三角形缺一角呢，这不是显而易见吗，从第二行显然左边才是n-2 而右边已经到了n-4，由此得知，右边完的快。
而这个时间复杂度怎么算呢 F(N)=2^0+2^1+2^2+...+2^（N-2） (1)
然后（1）式*2 （2）
然后（2）式-（1）式得 F(N)=2^N-1 也可以用等比数列求和。
显然看出他的时间复杂度为O(N)
实例7：
// 计算阶乘递归Fac的时间复杂度？
long long Fac(size_t N)
{
if (0 == N)
return 1;
return Fac(N - 1) * N;
}
这是一个关于递归的代码，我们要注意：递归算法时间复杂度是多次调用的次数叠加。由此我们我们来分析以上代码。
由此我们得出他的时间复杂度为F(N)
好的实例结束还有两道oj题，可见一下篇博客。