人工智能预测更好的抗癌药物组合

所以最后我们说：这个算法的算法时间复杂度是O(n^2) 。

也可以用另一种简化的思路，其实当n大于40的时候， 这个复杂度会恒小于O(3 * n^2)， O(2 * n^2 + 10 * n + 1000) < O(3 * n^2)，所以说最后省略掉常数项系数最终时间复杂度也是O(n^2)。

O(logn)中的log是以什么为底?

平时说这个算法的时间复杂度是logn的，那么一定是log 以2为底n的对数么?

其实不然，也可以是以10为底n的对数，也可以是以20为底n的对数，「但我们统一说 logn，也就是忽略底数的描述」。

为什么可以这么做呢?如下图所示：
 

时间复杂度，不同数据规模的差异

在决定使用哪些算法的时候，不是时间复杂越低的越好(因为简化后的时间复杂度忽略了常数项等等)，要考虑数据规模，如果数据规模很小甚至可以用O(n^2)的算法比O(n)的更合适(在有常数项的时候)。

就像上图中 O(5n^2) 和 O(100n) 在n为20之前 很明显 O(5n^2)是更优的，所花费的时间也是最少的。

那为什么在计算时间复杂度的时候要忽略常数项系数呢，也就说O(100n) 就是O(n)的时间复杂度，O(5n^2) 就是O(n^2)的时间复杂度，而且要默认O(n) 优于O(n^2) 呢 ?

这里就又涉及到大O的定义，「因为大O就是数据量级突破一个点且数据量级非常大的情况下所表现出的时间复杂度，这个数据量也就是常数项系数已经不起决定性作用的数据量」。

例如上图中20就是那个点，n只要大于20 常数项系数已经不起决定性作用了。

「所以我们说的时间复杂度都是省略常数项系数的，是因为一般情况下都是默认数据规模足够的大，基于这样的事实，给出的算法时间复杂的的一个排行如下所示」：

O(1)常数阶 < O(logn)对数阶 < O(n)线性阶 < O(n^2)平方阶 < O(n^3)(立方阶) < O(2^n) (指数阶)

但是也要注意大常数，如果这个常数非常大，例如10^7 ，10^9 ，那么常数就是不得不考虑的因素了。

复杂表达式的化简

有时候我们去计算时间复杂度的时候发现不是一个简单的O(n) 或者O(n^2)， 而是一个复杂的表达式，例如：
 

相信每一位录友都接触过时间复杂度，「代码随想录」已经也讲了上百道经典题目了，是时候对时间复杂度来一个深度的剖析了，很早之前就写过一篇，当时文章还没有人看，Carl感觉有价值的东西值得让更多的人看到，哈哈。

所以重新整理的时间复杂度文章，正式和大家见面了!

究竟什么是时间复杂度

「时间复杂度是一个函数，它定性描述该算法的运行时间」。

我们在软件开发中，时间复杂度就是用来方便开发者估算出程序运行的答题时间。

那么该如何估计程序运行时间呢，通常会估算算法的操作单元数量来代表程序消耗的时间，这里默认CPU的每个单元运行消耗的时间都是相同的。

假设算法的问题规模为n，那么操作单元数量便用函数f(n)来表示，随着数据规模n的增大，算法执行时间的增长率和f(n)的增长率相同，这称作为算法的渐近时间复杂度，简称时间复杂度，记为 O(f(n))。

什么是大O

这里的大O是指什么呢，说到时间复杂度，「大家都知道O(n)，O(n^2)，却说不清什么是大O」。

算法导论给出的解释：「大O用来表示上界的」，当用它作为算法的最坏情况运行时间的上界，就是对任意数据输入的运行时间的上界。

同样算法导论给出了例子：拿插入排序来说，插入排序的时间复杂度我们都说是O(n^2) 。

输入数据的形式对程序运算时间是有很大影响的，在数据本来有序的情况下时间复杂度是O(n)，但如果数据是逆序的话，插入排序的时间复杂度就是O(n^2)，也就对于所有输入情况来说，最坏是O(n^2) 的时间复杂度，所以称插入排序的时间复杂度为O(n^2)。

同样的同理再看一下快速排序，都知道快速排序是O(nlogn)，但是当数据已经有序情况下，快速排序的时间复杂度是O(n^2) 的，「所以严格从大O的定义来讲，快速排序的时间复杂度应该是O(n^2)」。

「但是我们依然说快速排序是O(nlogn)的时间复杂度，这个就是业内的一个默认规定，这里说的O代表的就是一般情况，而不是严格的上界」。如图所示：

（编辑：广元站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!