关于算法的时间复杂度的简单理解
在程序设计和编程中，我们经常会看到关于时间复杂度的讨论。比如为什么A方法比B方法好？是因为A方法的时间复杂度低。那么，这里的时间复杂度如何去理解，又怎么计算呢？常见的O(n)的含义是什么？本文将简单的解释这个概念。本文参考了清华大学邓俊辉老师的数据结构课程，值得大家学习。
一、简介
在关于程序算法的介绍中，比较算法的效率是一个非常常见的行为。我们经常看到某些算法的介绍中，描述某个算法的时间复杂度是O(n)。这是大O符号表示的时间复杂度（Big O Notation）。它的含义就是说这个算法的最差情况下，其操作次数会随着数据数量级的增长会是线性增长的。这个说法看起来好像比较晦涩，我们来逐一解释一下这个问题。
二、关于算法的效率比较
在说明这个概念之前，我们先简单解释一下关于算法的比较问题。一般来说，算法的执行速度与软硬件都有很大的关系，不同的编程语言、不同的编程方式、不同的硬件平台会导致相同的方法在运行效率上出现很大的差异。显然，我们不能简单地用耗时多久来表示某个算法的运行速度。那么，为了屏蔽这些软硬件差异来对算法进行比较，一个可行的思路就是将算法的执行时间转成算法需要执行的步骤数量来比较。因为无论什么编程语言实现的什么算法，在当前的计算机系统中最后都会变成CPU执行某个指令。如果我们能把算法的运行过程用执行多少次指令来估算，那么这样的话不同算法之间的执行速度就有一个公平的比较了。 但是，仅仅做这样的转换显然还是不够的。因为，即便是同样的算法，同样的数据规模，针对不同数据分布，算法的运行时间也是不一样的。例如，以在列表中查找是否包含某个元素为例。假设我们有如下两个列表：
列表1：
[1,2,3,4,5]
列表2：
[5,4,3,2,1]
如果我们要查找列表是否包含元素1，然后从列表第一个元素开始比对。那么显然第一个列表比对一次就可以返回Yes，而第二个列表需要比对5次才能返回Yes。显然，不同的数据分布也会对算法的运行速度产生影响。那么，为了屏蔽这种差异，一般来说对于算法的运行效率我们有三种可以计算的指标：最好的情况，最差的情况和平均情况。
以下图为例，假设T(n)是某个方法关于输入规模的一个函数，纵轴表示当前输入规模下，算法的时间复杂度，可以看到，n一定情况下，不同输入的分布T(n)会有一个最优的情况，也就是时间复杂度最低，用$\Omega(n)$表示，也有一个最差的情况，用$O(n)$表示，意思是最坏的情况下，这个方法的效率。其它的情况都是介于二者之间。
