1、什么是时间复杂度？
- 首先，解决一个问题肯定有许多种方式可以实现，那么如何评价一个算法的好坏？处理相同的数据量，用时更少，用的空间更少。
- 那么如何估算一个程序的运行时间与数据量的关系，这个函数就是算法的时间复杂度。时间复杂度可被称为是渐近的，程序指令运算次数。
- 空间复杂度是算法在运行过程中临时占用存储空间大小的量度。
2、如何计算时间复杂度？
- 既要知道常见算法的复杂度，也要会分析自己程序的具体复杂度。
- 常见的有
O（n）：KMP,欧拉筛法
O（nlogn）：线段树
O（n^2）：某些dp
O（n^3）：Floyd
O（2^n）：二进制枚举
O（n！）：枚举排列 - 自己分析
树的递归，logn
一层循环：n
。。。。。 - 更多请转维基百科balabala的
2、如何在算法题中运用时间复杂度？
- 算法竞赛一般给出1s的时间限制和256MB的空间限制。
- 对于1s的时间，能跑多少数据
O（logn）：很大，longlong以内都行
O（n）：10的7次方，也就是1000万的数据
O（nlogn）：5*10^5，大约50万的数据
O（n^2）：1000-5000左右
O（n^3）：200-500左右
O（2^n）：20-25
O（n！）：12左右 - 对于256MB的空间，
一个int，32位，4个字节。256=2^28 = 67,108,864个in
也就是6*10^7的数据，如果是long long，那么少一半就可以了。