Какие обозначения Big O у меня здесь? - PullRequest
Новая
       32

Какие обозначения Big O у меня здесь?

0 голосов
/ 29 сентября 2019

Так что я с трудом разбираюсь в обозначениях 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 (журнал N)?

Как вы видите, я немного догадываюсь, поэтому, если бы у вас был какой-либо совет о том, как определить правильное обозначение Big O, я был бы очень благодарен!

1 Ответ

1 голос
/ 29 сентября 2019

Вы правы в первом случае, и ваши рассуждения верны.

Действительно, сложность O (logn) во втором случае. Вот один из способов обдумать это:

На каждом шаге рекурсии вы делите число на два, пока не достигнете базового варианта, равного единице. Таким образом, количество раз, которое эта функция вызывается, является количеством раз, которое вы можете разделить число на два, пока не достигнете одного, что по определению является именно log (n). Каждый раз, когда вы вызываете функцию, вы выполняете O (1) операций, и, таким образом, общая сложность составляет O (logn).

...