时间复杂度和空间复杂度

时间复杂度和空间复杂度作为算法的核心概念；任何算法的优劣都可以以时间复杂度和空间复杂度来衡量；在大多数情况下，时间复杂度和空间复杂度是冲突的，但是在某些情况下，时间复杂度和空间复杂度在某个算法中都可以很小，这种情况下，该种算法就是最优解了；
但是并不是所有的算法都能兼顾两种复杂度保持简单，因此，更多的情况下，我们需要按照需求，有选择性的选择时间复杂度更低或者空间复杂度更低的算法；相当于牺牲时间换取空间，或者反过来牺牲空间，换取时间；

时间复杂度

时间复杂度用于描述，一段代码完成指定任务，需要多长时间可以完成；对于程序而言，很多情况下是在重复执行某一个事情，无论是循环亦或者是递归，某段代码的执行次数并不是一次，我们使用时间复杂度T(N)=O(?)的形式表示完成某一种算法，所需要的执行时间； 其实本质上就是某个代码段被执行了多少次…

O(1)常数时间

如果某个算法的执行时间与输入没有关系，例如，在数组中取出一个指定的内容；此时，时间复杂度就是一个常数值，这种情况下，我们称之为O(1)，常数时间；
当然，就算需要从数组中取出两个内容，T(n)=O(1)而不是T(n)=O(2)，这点并不难理解…其实O(1)表示常数时间是一个标准写法，非标准写发还可以将线性时间记作O(c)，其中c是一个常数；

O(n)线性时间

线性时间表示，某个算法的完成所消耗的时间，会随着输入内容的增加而线性增加的，例如，让数组中的每个内容自加，随着数组长度的增加，每增加一个内容，自加操作就会多执行一次；这就是所谓的线性时间；
在实际的执行中，当然也会出现T(n)=an+bn+c这种操作…但是只要还是一个线性函数，那么该算法的时间复杂度就是线性时间复杂度；

O(logn)对数时间

对数时间表示，某个算法的完成所消耗的时间，随着输入内容的增加而增加，但是这种增加是符合对数函数规律的，也就是说 随着输入内容的增加，新增加的内容为整体处理时间带来的消耗增量主键减少 ；
例如常见的二分法，假设现在存在一个有序的长度为n的数组，使用二分法查找，需要执行2^m>=n次；此时二分代码查询次数m=log，对与这种类型的时间复杂度，我们一般不关注对数底，而是统一的将他们称之为对数时间，记作O(longn)；

O((logn))幂对数时间

据说在分布式系统中幂对数时间是比较重要的….但是我没有找到合适的例子

O(n)平方时间

显而易见的是，这个时间复杂度会随着n的增大而增大，增量还不小…在循环的嵌套中经常会遇到这种时间复杂度

for(int i=0;i<n;i++)
{
    for(int j=0;j<n;j++)
    {
        //some O(n) code
    }
}

与此类似的还有O(n^3)时间复杂度。递归中也会见到类似的时间复杂度；

O(2^n)指数时间

一般认为这种算法在时间复杂度上的表现是很糟糕的…因为随着n的增大，处理时间的增量是指数上升的，就像阿凡提的棋盘一样，最后一个棋盘的格子中，倾尽国王的粮库也填不满

O(n!)

这种时间复杂度和O(2^n)有异曲同工之妙…在n足够大的时候..每次n++，处理时间增量为[(n+1)n]/2，这种时间复杂度也是需要尽量避免的；

时间复杂度的优越性

O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!)
毫无疑问，常数时间复杂度是最好的，但是实际使用过程中，能达到O(logn)乃至O(n)或者是O(nlogn)就是较好的算法了，n^2,n^3在某些时候也是可以接受的，但是如果时间复杂度为2^n或者n！，就需要好好审查一下，优化算法；