时间复杂度

2024-01-23 08:56:16

一、写在前面

在分析二分查找法时，看到O(1),O(N),O(logn),O(nlogn)等时间复杂度的表达式，经过一番分析才最有所了解，并记录之。

时间复杂度个人认为就是不同的算法（程序）在执行时所消耗的时间维度，不同的算法结果相同但是消耗时间不同，优秀算法肯定时间复杂度低。

时间复杂度通用表示方法

「 大O符号表示法 」，即 T(n) = O(f(n))，在大O符号表示法中，时间复杂度的公式是： T(n) = O( f(n) )，其中f(n) 表示每行代码执行次数之和，而 O 表示正比例关系，这个公式的全称是：算法的渐进时间复杂度。

int sum(int n) {
①   int value = 0;
②   int i = 1;
③   while (i <= n) {
④       value = value + i;
⑤       i++;
    }
⑥   return value;
}
假设n=100，该方法的执行次数为①(1次)、②（1次）、③（100次）、④（100次）、⑤（100次）、⑥（1次），假设每执行一次需要时间是1ms那么程序执行完完毕需要
合计1+1+100+100+100+1 = 303ms

按照上面的例子 f(n)=3n+3,即O=3n+3，从这个结果可以看出，这个算法的耗时是随着n的变化而变化，因此，我们可以简化的将这个算法的时间复杂度表示为：T(n) = O(n)

为什么可以这么去简化呢，因为大O符号表示法并不是用于来真实代表算法的执行时间的，它是用来表示代码执行时间的增长变化趋势的。

这里有个重点是时间复杂度关系的是数量级，原则是：

省略常数，如果运行时间是常数量级，用常数1表示；
保留最高阶的项
变最高阶项的系数为1

所以上面的例子中，如果n无限大的时候，T(n) = 3n+3中的常量3就没有意义了，倍数3也意义不大。因此直接简化为T(n) = O(n) 就可以了。

二、高中数学

（一）指数函数

函数 y = a^x （a>0且 a≠1）被称作为指数函数，自变量x叫做指数，a被称为底数。

（二）对数函数

如果ax =N（a>0，且a≠1），那么数x叫做以a为底N的对数，记作x=logaN，读作以a为底N的对数，其中a叫做对数的底数，N叫做真数。

三、常见的时间复杂度量级

（一）常数阶O(1)

HashMap map =new HashMap<>();
map.get(key);
比如从hash表中获取指定key的值，不会随着key的数量增多而增加程序的时间复杂度。

即 T(n) = O(1)

（二）对数阶 O(logn)

// n = 32 则 i=1,2,4,8,16,32
for (int i = 1; i <= n; i = i * 2) {
    System.out.println("对数阶：" + n);
}

i 的值随着 n 成对数增长，读作 2 为底 n 的对数，即 f(x) = log2n，T(n) = O( log2n)，简写为 O(logn)，还有其它算法比如二分查找法，时间复杂度也是 O(logn)

（三）线性阶 O(n)

for (int i = 1; i < n; i++) {
    System.out.println("线性阶：" + n);
}
n 的值为多少，程序就运行多少次，类似函数 y = f(x)，即 T(n) = O(n)

（四）线性对数阶 O(nlogn)

for (int m = 1; m <= n; m++) {
    int i = 1;
    while (i < n) {
        i = i * 2;
        System.out.println("线性对数阶：" + i);
    }
}

线性对数阶 O(nlogn)是指将对数阶 O(logn)的代码循环 n 遍执行，那么它的时间复杂度就是 n * O(logn)，也就是了 O(nlogn)，归并排序的复杂度就是 O(nlogn)。

若 n = 2 则程序执行 2 次，若 n=4,则程序执行 8 次，依次类推

（五）平方阶 O(n²)

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        System.out.println("平方阶：" + n);
    }
}

若 n = 2，则打印 4 次，若 n = 3，则打印 9，即 T(n) = O(n2)

四、总结

以上五种时间复杂度的图形描述如下

从上图可以得出结论，当 x 轴 n 的值越来越大时，y 轴耗时的时长为：

O(1) < O(logn) < O(n) < O(nlogn) < O(n²)

码农公寓