java:Big-Oh这个do-while代码片段的顺序?再加上一个紧的上界
问题描述:
我知道这很容易,但我的教科书并没有讨论带有do-while循环的Big-Oh命令,也没有使用我的其他算法源。java:Big-Oh这个do-while代码片段的顺序?再加上一个紧的上界
此问题表明以下代码片段参数化变量“n”,并且还需要紧上限。
int i=0, j=0;
do {
do {
System.out.println("...looping..."); //growth should be measured in calls to println.
j=j+5;
} while (j < n);
i++;
j = 0;
} while (i < n);
任何人都可以帮我解释Big-Oh命令的do-while循环吗?它们和循环一样吗?
答
一个很好的格言与嵌套循环和大O的工作是
“有疑问时,从内到外的工作!”
这里是你已经发布的代码:
int i=0, j=0;
do {
do {
Do something
j=j+5;
} while (j < n);
i++;
j = 0;
} while (i < n);
让我们看看内部循环。它大概运行n/5次,因为j从0开始并在每一步增加5。 (我们还可以看到,在循环开始之前,j总是被重置回0,无论是在循环外部还是在内部循环结束时)。因此,我们完全可以替代的东西,基本上说,内部循环“为此,我们关心Θ(n)的操作,”像这样:
int i=0;
do {
do Θ(n) operations that we care about;
i++;
} while (i < n);
现在我们只需要看看有多少工作这样做。请注意,这将循环Θ(n)次,因为我计数0,1,2,...,直到n。最终结果是这个循环运行了Θ(n)次,并且因为我们在每次迭代时都会执行Θ(n)操作,所以最终的效果是这样做的打印输出结果是Θ(n )你正在努力数数。
看起来像O(n^2) –
您用于获取迭代的语法是不相关的。不管语法如何,你只需要计算迭代次数依赖于什么。 – EJP
循环是一个循环。当你看到一个循环内的循环时,认为O(n^2)。我知道这不是直接相关的,但是[Big-O](http://bigocheatsheet.com/) –