java - 有人可以向我解释一下获得此 java 代码 BigO/运行时间答案的正确步骤吗？

Question

sum = 0;
 for(i=0;i<sqrt(n)/2;i++)
sum++;
 for(j=0;j<sqrt(n)/4;j++)
sum++;
for(k=0; k<8+j; k++)
 sum++; 

问题是，如果 n = 100 的程序运行需要 10 毫秒，那么 40 毫秒可以解决多大的问题。答案是 1600。我的问题是他们是如何达到 1600 的，我尝试将其插入 N，但我一直得到 200？我应该插入第一个 N 环路还是第二个 N 环路？

Answer 1

考虑循环运行的次数。第一个用于 sqrt(n)/2 迭代，第二个 sqrt(n)/4 迭代，最后一个用于 8 + j，其中 j是某个值(循环中的常数)。因此，对于整个代码，我们的复杂度为 sqrt(n)/2 + sqrt(n)/4 + 8 + j。为了获得 Big O 表示法，我们采用其中增长最快的一个，忽略常量，即 sqrt(n)。这表明对于较大的 n，代码的运行时间为 sqrt(n) 。现在我们只需找到一个满足 sqrt(n) = 40 的 n，即 40^2 = 1600。

还要注意，考虑到 Big O 表示法仅处理与 n 的大值的比较(因为我们忽略常量和大多数项)，这个问题有点愚蠢。因此，用它们进行任何形式的计算确实非常奇怪。