前言
时间复杂度主要是为了反映函数的执行时间随着输入规模增长而变化的规律，在一定程度上可以体现程序的执行效率和算法的优劣。作为程序员，掌握基本的算法时间复杂度的计算是很有必要的。
时间复杂度介绍
理论上，执行一个算法消耗的时间，是无法精确计算的，即使上机测试，收到各种因素影响，得到的时间也可能有较大差别。对于程序员，我们只需关注哪个算法花费的时间多，哪个算法花费的时间少就可以了。
针对执行时间，我们可以根据算法执行的语句的次数，进行一个简单的衡量。理论上，一个算法中语句执行次数多，它花费时间相对也多，因此，算法运行的时间与算法中语句的执行次数成正比。我们将算法中的语句的执行次数称为时间频度，表示为T(n)，其中，n表示算法的输入规模，n的变化会引起T(n)的改变。
为了得到T(n)变化时表现的规律，我们引入时间复杂度的概念。若有某个函数f(n),当n趋近于无穷大时，T(n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数，表示为T(n)=Ｏ(f(n))，Ｏ(f(n))称为算法的渐进时间复杂度，简称时间复杂度。
举例说明如何得到时间复杂度
场景1：
1. public int func() {
2. int a = 10 + 20; // 执行 1 次
3. return a; // 执行 1 次
4. }
T(n) = 1 + 1 = 2
由于是常数，时间复杂度为O(1)
场景2：
1. public void func() {
2. int n = 10; // 执行1次
3. for(int i = 0; i < n; i++) { // 执行 n 次
4. System.out.printf(i); // 执行 n 次
5. }
6. }
T(n) = n + n + 1 = 2n + 1
忽略常数项1，忽略和最高阶相乘的常数2，得到时间复杂度O(n)
其实，还可以先计算每个语句的时间复杂度，然后汇总：
1. public void func() {
2. int n = 10; // 时间复杂度O(1)
3. for(int i = 0; i < n; i++) { // 时间复杂度O(n)
4. System.out.printf(i); // 时间复杂度O(1)
5. }
6. }
O(1 * n * 1) = O(n)
场景3：
1. public int func(int n) {
2. for(int i = 0; i < n; i++) { // 执行n次
3. for(int j = 0; j < n; j++) { //由于外层循环，该语句执行 n * n 次
4. System.out.printf("Hello"); // 同理，执行n*n次
5. }
6. }
7. }
T(n) = n + n^2 + n^2 = 2n^2 + n
忽略低阶项，和高阶项的常数部分，得到时间复杂度O(n^2)
场景4：
1. public int func(int n) {
2. for(int i = 0; i < n; i = i* 2) { // i=2,4,8,16...时执行，可通过对数近似计算次数，执行log2(n)次
3. System.out.printf("Hello");
4. }
5. }
T(n) = 2log2(n)
忽略常数部分，得到时间复杂度O(log2(n))
总结
计算时间复杂度时，可以先先计算 T(n)，然后忽略常数项，只保留最高次项，同时忽略最高项的系数，得到函数 f(n)，则算法的时间复杂度就是 O(f(n))。
网友评论