Сложность времени следующего великого элемента - PullRequest
Новая
       7

Сложность времени следующего великого элемента

0 голосов
/ 28 июня 2018

Я решил проблему Next Greater Element со ссылкой на этот вопрос от GeeksforGeeks. Я совсем запутался, чтобы найти временную сложность (Big O) для следующей задачи. Было бы очень полезно, если бы кто-нибудь мог помочь мне в этом.

Вопрос: Для данного массива выведите Next Greater Element (NGE) для каждого элемента. Следующий больший элемент для элемента x - это первый больший элемент с правой стороны от x в массиве. Элементы, для которых не существует большего элемента, рассматривают следующий больший элемент как -1.

Примеры:

a) Для любого массива самый правый элемент всегда имеет следующий больший элемент как -1.

b) Для массива, отсортированного по убыванию, все элементы имеют следующий больший элемент как -1.

    Как найти временную сложность этого?

    Это приемлемый способ решения этой проблемы? 

        int[] array = {20,10,5,3};

    int len =array.length;
    int[] temp = new int[len];

    int j=0;
    int i=j;
    while(j<len-1){
        ++i;
        if(i>=len){
            System.out.println(array[j]+"----> -1");
            j++; i=j;
            continue;
        }
        if(array[j]<array[i]){
            System.out.println(array[j]+"----> "+array[i]);
            j++; i=j;
        }
    }
    System.out.println(array[j]+"----> -1");

    1 Ответ

    0 голосов
    / 28 июня 2018

    Вы испытываете трудности с определением сложности вашего алгоритма, потому что вы используете continue, что добавляет ненужные трудности вашим рассуждениям.

    Переписать следующее (без использования break или continue): 

    public void test() {
    int[] array = {10, 20, 3, 5};

    int len = array.length;

    for (int j = 0; j < len - 1; j++) {
        int nge = -1;
        for (int i = j + 1; i < len && nge < 0; i++) {
            if (array[j] < array[i]) {
                nge = array[i];
            }
        }
        System.out.println(array[j] + "----> " + nge);
    }
    System.out.println(array[len-1] + "----> -1");
}

    Теперь ясно, что это O(n lg n), потому что внешний цикл повторяется до n, а внутренний до n - j.

    ...