什么是时间复杂度

作为一个处在学习之路的渣渣，被一个时间复杂度的题给难倒了，然后我就思考了一下什么是时间复杂度。虽然在学校学习了了算法的课程，但是仔细一想，对于时间复杂度还真是不怎么懂。于是重新学习，记下自己的一些理解。

1.时间复杂度

提到时间复杂度，第一时间想到的是算法，简单说，算法就是你解决问题的方法，而你用这个方法解决这个问题所执行的语句次数，称为语句频度或者时间频度，记为T(n)。

那么问题来了，我们为什么要引入这些个概念呢。因为我们想要的是执行一个算法耗费的时间，这个时间理论上可以得到，但是，要得到这个时间就必须要上机测试，但是有这个必要吗？我们需要知道的是哪一个算法需要的时间多，哪一个算法需要的时间少，这样就可以了。而且，算法的耗时和语句的执行次数是成正比的，即语句执行越多，耗时越多。这也就是我们引入概念的原因。

在上面提到的时间频度T(n)中，n是指算法的规模，n不断的变化，T(n)就会不断的变化，而这些变化的规律是怎样的呢？于是我们引入了时间复杂度的概念。

什么是时间复杂度，算法中某个函数有n次基本操作重复执行，用T(n)表示，现在有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。通俗一点讲，其实所谓的时间复杂度，就是找了一个同样曲线类型的函数f(n)来表示这个算法的在n不断变大时的趋势 。当输入量n逐渐加大时，时间复杂性的极限情形称为算法的“渐近时间复杂性”。 

我们用大O表示法表示时间复杂性，它是一个算法的时间复杂性。大O表示只是说有上界但并不是上确界。

“大O记法”：在这种描述中使用的基本参数是 n，即问题实例的规模，把复杂性或运行时间表达为n的函数。这里的“O”表示量级 (order)，比如说“二分检索是 O(logn)的”,也就是说它需要“通过logn量级的步骤去检索一个规模为n的数组”记法 O ( f(n) )表示当 n增大时，运行时间至多将以正比于 f(n)的速度增长。 

时间复杂度对于算法进行的分析和大致的比较非常有用，但是真正的情况可能会因为一些其他因素造成差异。比如一个低附加代价的O(n2)算法在n较小的情况下可能比一个高附加代价的 O(nlogn)算法运行得更快。但是，n越来越大以后，相比较而言较慢上升函数的算法会运行的更快。

上面我引用了一些专业的定义，可能并不是太好理解，下面会写一些常出现的算法时间复杂度和一些实例来解释一下。

2.简单算法的时间复杂度举例

列举一些简单例子的时间复杂度。

O(1)的算法是一些运算次数为常数的算法。例如：

    temp=a;a=b;b=temp;

上面语句共三条操作，单条操作的频度为1，即使他有成千上万条操作，也只是个较大常数，这一类的时间复杂度为O(1)。

O(n)的算法是一些线性算法。例如：

    sum=0；                 

     for(i=0;i