很难找出这些棘手的大O的例子

Question

我正在为即将到来的关于大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;
            }
       }`

对于这一个，外部循环中的i=i*2意味着O（log（n）），我认为i

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）？我以前从未见过这样的例子，所以现在我几乎是在猜测。这个问题的大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）并试图欺骗你。所以对于这个问题，大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 

很明显，“我”成长得很快，所以这个条件很快就满足了。然而，我不确定这是什么样的大O符号。

非常感谢你能给的任何提示或提示，谢谢伙计们。




Answer 1

不能将i或j添加到O表示法中，必须将其转换为n。

对于第一个：

设k为log2i。

然后，对于外循环的每次迭代，内循环执行2^（k*3）/2=2^（3k-1）次。

k从1到log2n。所以总迭代次数是2^（3k-1）的总和，对于k从1到log 2n，根据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^（12…k）

所以1 2 3... k=log 2 n

（k1）k/2=log2n

哪个是O（sqrt（logn））

顺便说一句，log n^2不是n。这个问题在计算机科学上比在这里问更好。