算法衡量标准之时间复杂度

什么是时间复杂度

时间复杂度作为衡量一个算法好坏的的重要标准，可以简单的理解为在其它条件（如运行环境、数据规模等）均相同的情况下，解决同一数据规模的的问题所花费的时间的多少。

由上述我们可知，一个算法的时间复杂度跟运行环境、数据规模均有关系，那我们应该怎样合理的衡量一个算法的时间复杂度。由此我们引入了另一个概念基本操作执行次数。

什么是基本操作执行次数

什么是基本操作执行次数，通过以下几个例子进行说明

• 场景一:
  吃一块西瓜需要3分钟，那么吃两块就需要6分钟，依次类推。那么如果要吃n块，则需要3n分钟。那么我可以得出T(n)=3n来解决这个问题.
• 场景二:
  有一个西红柿和一个黄瓜，每吃完一个黄瓜需要3分钟，所以不管有多少个西红柿，吃完黄瓜需要的时间都是3分钟。那么可以得出T(n)=3.
  上述两个场景的例子中的花费的时间，在程序中可以理解为程序的基本操作执行次数。我们可以假设T(n)为程序执行次数相关的函数，n则为程序的数据规模。

如何推导时间复杂度

1. 如果运行时间是常数，则用常数1表示。
2. 只保留时间函数中的最高项。
3. 如果最高阶存在，则可以省去最高阶前面的系数。

我们常见的时间复杂度的关系是：O(1)<O(logn)<O(n)<O(n^2)