Будет ли этот пример O (n) или O (nlogn)? - PullRequest
Новая
       5

Будет ли этот пример O (n) или O (nlogn)?

0 голосов
/ 21 октября 2018

Мне просто нужно немного разъяснить этот аспект большого O -

Если бы у нас был метод, у которого была функция O (logn), прежде чем перейти к функции O (n), был бы общий большой Oметод будет O (N), а не O (nlogn)?Например, сортировка массива (функция O (logN)), за которой следует цикл for, который перебирает массив.

1 Ответ

0 голосов
/ 21 октября 2018

Это зависит от того, как метод вызывается.

См. Приведенный ниже пример: 

// O(n)
void iterate(int[] array) { 
    for(int i = 0; i < array.length; i ++) {
        // ...
    }
}

// O(n^2)
void doubleIterate(int[] array) {
    for(int i = 0 ; i < array.length ; i ++){
        for(int j = 0 ; j < array.length ; j ++) {
            // ...
        }
    }
}

Если вы вызываете iterate извне цикла for для doubleIterate, сложность всего метода равна O(n^2). 

// O(n^2) + O(n) = O(n^2 + n) = O(n^2)
void doubleIterate(int[] array) {
    for(int i = 0 ; i < array.length ; i ++){
        for(int j = 0 ; j < array.length ; j ++) {
            // ...
        }
    }
    iterate(array);
}

Если вы вызываете iterate из первого цикла doubleIterate, сложность все равно O(n^2). 

// O(n*(n+n)) = O(2*n^2) = O(n^2)
void doubleIterate(int[] array) {
    for(int i = 0 ; i < array.length ; i ++){
        for(int j = 0 ; j < array.length ; j ++) {
            // ...
        }
        iterate(array);
    }
}

Если вы вызываете iterate из внутреннего цикла doubleIterate сложность всего метода составляет O(n^3). 

// O(n^2*n) = O(n^3)
void doubleIterate(int[] array) {
    for(int i = 0 ; i < array.length ; i ++){
        for(int j = 0 ; j < array.length ; j ++) {
            // ...
            iterate(array); 
        }
    }
}
...