use*_*503 5 complexity-theory big-o time-complexity
我无法找到这段代码的Big-O表示法.我需要找到for循环的表示法.
public static int fragment(int n)
{
int sum = 0;
for (int i = n; i >= 1; i /= 2)
{
for (int j = 1; j <= i; j *= 3)
{
sum++;
}
}
return sum;
}
分别考虑两个循环：
首先让我们考虑for(int i=n; i>=1; i/=2)每次迭代时 的值i将除以 2，直到达到小于 的值1。因此，迭代次数 N 将等于在它小于 1 之前应除的次数。有一个众所周知的函数表示这个i数字- 。2log(n)
现在让我们考虑内循环。for(int j=1;j<=i; j*=3)。这里将 j 乘以 3，直到它大于i。如果您稍微想一下，这与对第一个循环进行以下轻微修改所执行的迭代次数完全相同：for(int j=i; j>=1; j/=3)。通过完全相同的解释，我们有相同的函数（但基数不同 - 3）。这里的问题是迭代次数取决于 i。
所以现在我们的总复杂度是：
log 3 (n) + log 3 (n/2) + log 3 (n/4) ... + log 3 (1) =
log 3 (n) + log 3 (n) - log 3 (2) + log 3 (n) .... - log 3 (2 log 2 (n) ) =
log 3 (n) * log 2 (n) - log 3 (2) - 2 * log 3 (2) - ... log 2 (n) * log 3 (2) =
log 3 (n) * log 2 (n) - log 3 (2) * (1 + 2 + ... log 2 ) =
log 3 (n) * log 2 (n) - log 3 (2) * (log 2 (n) * (log 2 (n) + 1)) / 2 =
log 2 (n) * (log 3 (n) - log 3 (2) * (log 2 (n) + 1) / 2) =
log 2 (n) * (log 3 (n) - (log 3 (n) + log 3 (2)) / 2) =
(log 2 (n) * log 3 (n)) / 2 - (log 2 (n) * log 3 (2)) / 2
计算有点棘手，我使用了对数的一些属性。然而最终的结论是循环是复杂的O(log(n)^2)（记住你可以忽略对数的底数）。