在 runtime 中的一些骚东西

根据上面的规律我们不难发现，那么2^执行次数=n，即 2^T(n)=n ，我们求 T(n)，调个就行了，也就是以 2 为底 n 的对数，即 T(n)=log_2 n

「PS：又来补数学了」

「对数：」 假如 a^n=b，即 a 的 n 次方等于 b，我们求 n 的值，那么这里为了方便表示就可以写成 log_a b，即以 a 为底 b 的对数，a 是底数，b 是真数，而 n 就是对数

你可能会在纠结为什么只观察循环中的打印次数而不计算其所有的执行次数，原因上面也说过了，这些固有的常数及系数完全可以忽略，好吧，我们再最后推一遍

中间输出为 log_2 n 次，let i = 1 只会执行一次，i

「例7：」

最后在给大家来一个例子吧
 

其实遇到这种，我们直接带入进去试一试即可知其规律

当 i = 0 时，里层循环会执行 n 次

当 i = 1 时，里层循环会执行 n - 1 次

当 i = 2 时，里层循环会执行 n - 2 次

当 i = 3 时，里层循环会执行 n - 3 次

这个时候我们就发现了规律，每当 i 增加 1，里层循环就少执行 1 次，那么就简单了

当 i = n - 2 时，里层循环会执行 2 次

当 i = n - 1 时，里层循环会执行 1 次

最终我们把 n 个里层循环的执行次数相加即可得出最终的一个不精确的总执行次数
 

这个题和上面就不太一样了，我们先单独看内部的循环，内部循环大概会执行 n 次，再来看外部循环又会执行 n 次，最终也就是 n * n = n^2，即函数 fn03 的时间复杂度为 O(n^2) ，此为平方级时间复杂度，如果是三层循环也就是时间复杂度为 O(n^3) 时，即立方级时间复杂度

从这里我们就可以看出来，一段代码有多少层循环，时间复杂度就是 n 的多少次方，所以尽量避免多层循环嵌套

「例4：」

我们再来看下面这个函数 fn04

（编辑：通化站长网）

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