很难找出这些棘手的Big-O示例
我正在为即将到来的关于Big-O记法的测验做准备。我这里有几个例子，但他们给我带来了麻烦。对于你在网上找到的许多基本示例来说，它们似乎有点太高级了。以下是我被困在这里的问题。
1. `for (i = 1; i <= n/2; i = i * 2) {
sum = sum + product;
for (j= 1; j < i*i*i; j = j + 2) {
sum++;
product += sum;
}
}`对于这个例子，外部循环中的对数表示O( i = i * 2 (N))，我认为i <= n/2条件不会改变任何东西，因为我们忽略了常量。因此，外部循环保持O(log(n))。内部循环条件j < i*i*i把我搞糊涂了，因为它是“i”而不是“n”。那么这个内部循环的Big-O会是O(i^3)吗？因此整个问题的大O是O( (i^3) * log(n) )？
2. `for (i = n; i >= 1; i = i /2) {
sum = sum + product
for (j = 1; j < i*i; j = j + 2) {
sum ++;
for (k = 1 ; k < i*i*j; k++)
product *= i * j;
}
}`对于这个循环，最外层的循环表示O(log(n))。中间的循环意味着，同样不确定，O(i^2)？最里面的循环意味着O(i^2*j)？我以前从来没有见过这样的例子，所以我几乎是在猜测这一点。这个问题的Big-O符号是O(i^4 *n* j)吗？
3. `for (i = 1; i < n*n; i = i*2) {
for (j = 0; j < i*i; j++) {
sum ++;
for (k = i*j; k > 0; k = k - 2)
product *= i * j;
}
}`这个循环最外面的循环有一个n^2的条件，但也有一个对数增量，所以我认为这就抵消成了规则的O(n)。中间的循环是O(i^2)，最里面的循环是O(n)，试图欺骗你。那么对于这个问题，Big-O符号应该是O(n^2 * i^2)？
4. `int i = 1, j = 2;
while (i <= n) {
sum += 1;
i = i * j;
j = j * 2;
}`
For this one I did a few iterations to better see what was happening:
i = 1, j = 2
i = 2, j = 4
i = 8, j = 8
i = 64, j = 16
i = 1024, j = 32 因此，很明显，“i”的增长非常快，因此条件很快就会得到满足。然而，我不确定这到底是哪种大O符号。
您能给出的任何建议或提示都将非常感谢，谢谢各位。
回答 1
Stack Overflow用户
发布于 2015-09-30 10:53:58
您不能将i或j添加到O表示法中，它必须转换为n。
对于第一个问题：
设k是log2i。
然后，对于外部循环的每次迭代，内循环被执行2^(k*3)/2=2^(3k-1)次。
K从1到log2n。因此，对于k从1到log2n，总迭代次数是2^(3k-1)之和，根据Wolfram Alpha，这是4/7(n^3-1)，即O(n^3)。
最后一个是i=j1*j2*j3*...jk和jm=2^m
i=2^1*2^2*...2^k=2^(1+2+...k)
所以1+2+3+...+k=log 2 n
(k+1)k/2 =log2 n
它是O(sqrt(log ))
顺便说一句，log n^2不是n。这个问题最好在计算机科学上问。
https://stackoverflow.com/questions/32856526
复制相似问题
腾讯云开发者
