我在这里有什么大符号？

Question

因此，我很难理解Big O符号，并且正在寻找一些示例以更好地理解它。现在让我们看下面的代码：

`public static void main(String[] args)` {

            int N = 4; 
           int sum = 0;

            for (int i = 1; i < N; i = i*2)
            {
                for (int j = 1; j < N; j++)
                {
                    sum++;
                }
            }

Am i assuming correctly that the Big O Notation here would be: O(N log(N))? Because the first for loop runs log(n) times and the second one does N times? If not: What would be the correct Big O Notation here? 


And another example: 

`public static int f(int N){

            if (N<=1)
            {
                return 0;
            }
            return (2*f(N/2));
        }`

Big O符号在这里是什么？是O（log N）吗？

您可以看到我的猜测有点多，因此，如果您对如何识别正确的Big O表示法有任何建议，我将不胜感激！

Answer 1

您对第一种情况是正确的，并且您的推理是正确的。

实际上，在第二种情况下，复杂度为O（logn）。这是一种思考的方法：

在递归的每一步中，将数字除以2，直到达到基数1。因此，调用此函数的次数是您可以将数字除以2直到达到1的次数，根据定义，精确地是log（n）。每次调用该函数时，都会执行O（1）操作，因此总复杂度为O（logn）。