我知道前两个循环的时间复杂度为 O(n^3),但我不确定 if 语句如何影响时间复杂度。
int sum = 0;
for(int i = 1; i < n; i++) {
for(int j = 1; j < i * i; j++) {
if(j % i == 0) {
for(int k = 0; k < j; k++) {
sum++;
}
}
}
}
最佳答案
if
语句对该代码的整体复杂性有巨大影响。
不使用 if 的复杂度为 O(n^5),但使用 if 的复杂度为 O(n^4)。
自 j
范围为 1 to i*i
if 仅当 j % i = 0
时才起作用.
这意味着对于每个 i, j
会工作i^2
还有i
情况下j % i = 0
.
因此,总体复杂度将为 O(n^4)
.
为了了解它是如何进行的,我只需编译代码:
static int count;
static void rr(int n)
{
for (int i = 1; i < n; i++)
{
for (int j = 1; j < i * i; j++)
{
if (j % i == 0)
{
for (int k = 0; k < j; k++)
{
count++;
}
}
}
}
}
public static void main(String[] args)
{
for (int n = 50; n < 110; n += 10)
{
count = 0;
rr(n);
System.out.println("For n = " + n + ", Count: " + count);
}
}
这是输出。
与 if
For n = 50, Count: 730100
For n = 60, Count: 1531345
For n = 70, Count: 2860165
For n = 80, Count: 4909060
For n = 90, Count: 7900530
For n = 100, Count: 12087075
没有 if
For n = 50, Count: 29688120
For n = 60, Count: 74520894
For n = 70, Count: 162068718
For n = 80, Count: 317441592
For n = 90, Count: 574089516
For n = 100, Count: 975002490
因此,如果复杂度为 O(n^4)。
关于algorithm - 这个 if 语句如何影响时间复杂度?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/59868331/