五分钟理解Java算法的时间复杂度

前言

时间复杂性主要是反映函数执行时间随输入规模的增加而变化的规律，在一定程度上反映了程序执行效率和算法的优缺点。作为一名程序员，有必要掌握算法时间复杂性的基本计算。

从理论上讲，执行算法所消耗的时间无法准确计算。即使在计算机测试中受到各种因素的影响，得到的时间也可能大不相同。对于程序员来说，我们只需要注意哪个算法需要更多的时间，哪个算法需要更少的时间。

对于执行时间，我们可以根据算法执行句子的数量进行简单的测量。理论上，算法中的句子需要更多的时间来执行，因此算法的运行时间与算法中句子的执行时间成正比。我们称算法中句子的执行次数为时间频率和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：

public int func() {int a = 10 + 20; // 执行 1 次return a; // 执行 1 次}T(n) = 1 + 1 = 2

由于是常数，时间复杂度为O(1)

场景2：

public void func() {int n = 10; // 一次for执行(int i = 0; i < n; i++) { // 执行 n 二级System.out.printf(i); // 执行 n 次}}T(n) = n + n + 1 = 2n + 1

忽略常数项1，忽略与最高阶相乘的常数2，获得时间复杂度O(n)

事实上，每个句子的时间复杂度也可以先计算，然后总结：

public void func() {int n = 10; // 时间复杂度O(1)for(int i = 0; i < n; i++) { // 时间复杂度O(n)System.out.printf(i); // 时间复杂度O(1)}O(1 * n * 1) = O(n)

场景3：

public int func(int n) {for(int i = 0; i < n; i++) { // 执行n次for(int j = 0; j < n; j++) { //由于外循环，该语句执行 n * n 二级System.out.printf("Hello"); // 同理，执行n*n次}}}T(n) = n + n^2 + n^2 = 2n^2 + n

忽略低阶项和高阶项的常数部分，获得时间复杂度O(n^2)

场景4：

public int func(int n) { for(int i = 0; i < n; i = i* 2) { // i=2,4,8,16...可通过对数近似计算时执行次数，执行log2(n)次 System.out.printf("Hello"); } } T(n) = 2log2(n)

忽略常数部分，得到时间复杂度O(log2(n))

在计算时间复杂度时，可以先计算 T(n)，然后忽略常数项，只保留最高次数，忽略最高项的系数，获得函数 f(n)，算法的时间复杂性是 O(f(n))。