我在这里有什么大 O 符号？

Question

所以我很难理解大 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) 吗？

如您所见，我有点猜测，所以如果您对如何识别正确的大 O 表示法有任何建议，我将不胜感激！

Answer 1

第一种情况你是对的，你的推理是正确的。

的确，第二种情况的复杂度是O(logn)。这是一种思考方式：

在递归的每一步中，您都将数字除以二，直到达到基本情况 1。因此，此函数被调用的次数是您可以将数字除以 2 直到达到 1 的次数，根据定义，这恰好是 log(n)。每次调用该函数时都会执行 O(1) 次操作，因此总复杂度为 O(logn)。

我在这里有什么大 O 符号？

What Big O notation do i have here?

java

theory

performance

big-o

runtime