当内循环为外循环中的每个log(N)计数时的时间复杂度
考虑这个函数：
void func()
{
int n;
std::cin >> n;
int var = 0;
for (int i = n; i > 0; i--)
for (int j = 1; j < n; j *= 2)
for (int k = 0; k < j; k++)
var++;
}
Ifn是一个常数，我认为时间复杂度是 O(n^2 * log n) 但是 when nis 2^m，我很难思考它是什么复杂度。
如何分析这个函数的复杂性？
回答
n不是常数，它是动态的，所以这是您分析中的变量。如果它是常数，则无论其值如何，您的复杂性都是 O(1)，因为在复杂性分析中所有常数都被丢弃。
同样，“n 是 2^m”有点荒谬，因为m它不是代码中的变量，所以我不确定如何分析它。复杂性分析是相对于输入的大小进行的；您不必引入更多变量。
让我们分解循环，然后将它们相乘：
for (int i = n; i > 0; i--) // O(n)
for (int j = 1; j < n; j *= 2) // O(log(n))
for (int k = 0; k < j; k++) // O(n / log(n))
for (int i = n; i > 0; i--) // O(n)
for (int j = 1; j < n; j *= 2) // O(log(n))
for (int k = 0; k < j; k++) // O(n / log(n))
总时间复杂度：O(n * log(n) * (n / log(n))) => O(n^2)。
前两个循环是微不足道的（如果第二个循环不明显，它是对数的，因为重复乘以 2，序列是1, 2, 4, 8, 16...）。
第三个循环更难分析，因为它运行于j，而不是n。我们可以通过完全忽略最外层循环，分析内层循环，然后将我们为两个内层循环获得的任何复杂度乘以最外层循环的 O(n) 来简化问题。
诀窍是查看封闭环的形状；随着j循环接近n，k从0..n线性开始，为循环提供 O(n) 的基线k。这是由对数因子jO(log(n))缩放的。对数因子取消，我们剩下 O(n) 用于内部循环。
以下是内部循环复杂性的一些经验证据：
这产生的情节是：
这表明最里面的两个循环（蓝色）是线性的，而不是线性的，一旦重新引入最外面的线性循环，就证实了整体二次复杂性。