我目前正在了解Big O Notation的运行时间。我尝试计算一些代码的时间复杂度：
int i = 1;
int n = 3; //this variable is unknown
int j;
while (i<=n)
{
for (j = 1; j < i; j++)
printf_s("*");
j *= 2;
i *= 3;
}
我认为该代码的复杂度为О（log n）。但是，即使是正确的，我也无法解释原因。
时间复杂度不是 O（log n），而是O（n）。
我们可以以结构化的方式进行计算。首先，我们检查内部循环：
for (j = 1; j < i; j++)
printf_s("*");
这里j从迭代1到i。因此，这意味着对于给定i，它将采取i-1步骤。
现在我们可以看一下外部循环，并且可以抽象出内部循环：
while (i<=n)
{
// ... i-1 steps ...
j *= 2;
i *= 3;
}
因此，while循环的每次迭代都将执行i-1步骤。此外，每次迭代都会i翻倍，直到大于n。因此，我们可以说该算法的步骤数为：
log3 n
---
\ k
/ 3 - 1
---
k=0
我们在这里使用k一个额外的变量，该变量开始于0并每次递增。因此，它计算了执行while循环主体的次数。它将在时结束3^k > n，因此我们将循环log 3（n）次，并且每次循环内部循环将以3 k -1的步长进行恢复。
以上金额等于：
log3 n
---
\ k
-log3 n + / 3
---
k=0
上面是一个几何级数[wiki]，它等于：（1-3 log 3 n）/（1-3），或者经过简化，它等于（n log 3 3 -1）/ 2，因此（n-1）/ 2。
因此，步骤总数由（n-1）/ 2-log 3 n限制，或更简单地用O（n）表示。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句