算法复杂度之时间复杂度
一 . 数据结构前言
1.1 数据结构
数据结构(Data structure) 是计算机存储，组织数据的方式，指互相之间存在一种或多种特定关系的数据元素的集合。没有一种单一的数据结构对所有用途都有用，所以要学习各式各样的数据结构，如：线性表，树，图，哈希等。（不仅能存储数据，还能够管理数据）
1.2 算法
算法 ( Algorithm) : 就是定义良好的计算过程 ， 取一个或一组的值输入，并产生处一个或一组值作为输出 。 （一系列的计算步骤 ， 用来将输入数据转化成输出结果）
数据结构和算法不分家 ----> 数据存储在内存中 ， 需要有算法 ； 有算法的地方 ，需要存储和管理数据（数据结构）；
二 . 算法效率
如何衡量一个算法的好坏 ? ----> 代码简洁?时间短?
看以下例题 :
旋转数组 : . - 力扣（LeetCode）
void rotate(int* nums, int numsSize, int k) {while (k--) {int end = nums[numsSize-1];for (int i = numsSize-1; i > 0; i--) {nums[i] = nums[i - 1];}nums[0] = end;}
}
代码测试可以通过 ， 但是点击提交的时候却无法通过 ，在面对大量的数据 ， 超出了时间限制 ，就说明这个算法 ， 还不太好 ， 那该怎样去衡量一个算法的好坏呢 ？
算法在编写成可执行程序后 ， 运行时需要耗费时间资源和空间（内存资源）。这么看来 ，衡量一个算法的好坏 ， 一般是从时间和空间两个维度来衡量 ，即时间复杂度和空间复杂度。
时间复杂度主要衡量一个算法的运行快慢 。 而空间复杂度主要衡量一个算法运行所需要的额外空间 。
在计算机发展早期 ， 计算机的存储容量很小 。 所以对空间复杂度很是在乎 。 但是经过计算机行业的迅速发展 ， 计算机的存储容量已经达到了很高的程度 ，而对算法空间复杂度的关注度有所下降。
三 . 时间复杂度
定义 ： 在计算机科学中 ， 算法的时间复杂度是一个函数式 T(N) , 它定量描述了该算法的运行时间 。 时间复杂度是衡量程序的时间效率 ， 那么为什么不去计算程序的运行时间呢？
使用clock 函数计算时间 代码如下：
#include <stdio.h>
#include <time.h>
int main()
{int t1 = clock();//当前时间//程序运行到当前程序的一个时间for (int i = 0; i < 100000; i++){for (int j = 0; j < 100000; j++){int a = 1;}}int t2 = clock();printf("%d\n", t2 - t1);return 0;
}
三次执行的时间都不相同 ， 程序执行的时间不仅和编译器有关 ， 而且还和CPU 的计算速度有关 ，并不能准确的计算出算法的运行的时间
为什么不去计算程序的运行时间呢？
- 因为程序运行时间和编译环境和运行机器的配置都有关系 ， 比如同一个算法程序 ， 用一个老编译器 和 新编译器编译 ， 在同样机器下运行时间不同。
- 同一个算法程序 ，用一个老低配置机器和新高配置机器 ， 运行时间也不同。
- 并且时间只能程序写好后测试 ， 不能写程序之前通过理想思想计算来评估。
时间复杂度是一个函数式 T(N) 到底是什么
思考：
所以只需要计算程序能代表增长量的大概执行次数 ，复杂度的表示通常使用 大O的渐进表示法；
3.1 大O的渐进表示法：
大 O 符号 （Big O notation) : 是用于描述函数渐进行为的数学符号
推导大O阶规则：
- 时间复杂度函数时T（N） 中 ，只保留最高阶的项 ， 去掉最低阶的项 ； 因为N不断变大，低阶项对结果影响越来越小 ， 但N无穷大时 ， 就可以忽略不计了。
- 如果高阶项存在 并且系数不是1 ， 则可以去掉这个项目的常数项系数 ， 因为当N不断增大的时候，这个系数对结果的影响越来越小，当N无穷大的时候，就可以忽略不计了。
- T(N) 中如果没有N相关的项目 ， 只有常数项 ， 用常数项1取代所有加法常数
所以 ， 以上例题的时间复杂度是 O(n^2)
3.2 示例1：
3.3 示例2：
3.4 示例3：
3.5 示例4：
在有些算法的时间复杂度存在最好 ， 平均 ，和最坏情况
最坏情况 ： 任意输入规模的最大运行次数（上界）
平均情况 ： 任意输入规模的期望运行次数
最好情况 ： 任意输入规模的最小运行次数（下界）
大O的渐进表示法在实际中一般情况关注的是算法的上界 ， 也就是最坏运行情况。
3.5 示例5：
3.6 示例6：
3.7 示例7：
