时间复杂度，在衡量算法效率时，经常被提及。
作为衡量算法效率的重要指标，我们需要对时间复杂度有一个更清晰和系统的认识。
本文主要介绍了时间复杂度的含义及其的计算方法。
算法基本概念
一个算法的效率主要从两方面来衡量，即执行所需的时间长短和所需的存储空间大小。也就是算法中的两个复杂度：
- 时间复杂度：评估执行程序所需的时间，可以估算出程序对处理器的使用程度。
- 空间复杂度：评估执行程序所需的存储空间，可以估算出程序对计算机内存的使用程度。
在算法的效率研究中，因为时间复杂度比空间复杂度更容易产生问题。因此主要研究的是时间复杂度，在不特别说明的情况下，算法的复杂度通常是指算法的时间复杂度。
时间复杂度
时间频度
一个算法花费的时间与算法中语句的执行次数成正比。可将算法中的语句执行次数称为时间频度或语句频度。记为T(n)。其中n 为问题的规模，类似需要排序的数组的长度，需要查询的元素的多少等。
当n不断变化时，时间频度T(n)也不断变化。也就是说时间频度T(n)是关于问题规模n的一个函数。
时间复杂度
为了呈现时间频度T(n)随问题规模n的变化而变化时呈现出的规律，引入了时间复杂度的概念。
若存在某个辅助函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不为0的常数，则称f(n)为T(n)的同数量级函数（最高阶数相同）。而此时有T(n)=O(f(n)),将O(f(n))称为算法的渐进时间复杂度，简称时间复杂度。表示随着问题规模n的增大，算法执行所需要的时间的增长可以用O(f(n))表示。
在判断
f(n)函数随n的变化而变化的规律时，最好和最准确的方法当然是求出函数的一阶导数。但在算法上，因为只需要大体了解算法的优劣即可，因此可以直接考虑f(n)函数中对增长速度影响最大的一项，即函数的最高阶数来评估算法的优劣。大O符号O()就是这样一种运算符号，作用为去除其他低阶项和与最高阶项相乘的常数，只保留最高阶项。
时间复杂度的计算
计算时间复杂度时，根据O(f(n))的定义，可得，f(n)去掉低阶项和最高阶项的常数后，即可得出时间复杂度。一般最高阶项可能值如下：
- 常数阶
O(1) - 线性阶
O(n) - 平方阶
O(n²) - 平方根阶
O(√n) - 立方阶
O(n³) - 对数阶
O(logn) - 指数阶
O(2ⁿ) - 线性对数阶
O(nlogn) - 阶乘阶
O(n!)
各阶数下时间频度和问题规模的曲线如下：
常用时间复杂度按照所需时间从小到大排序为:
1 | O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n³) < O(2ⁿ) < O(n!) |