Сложность времени выполнения для цикла Two for в цикле One for

Question

Я пишу Java-метод, который находит индексы стабильности для массива.Мой алгоритм работает нормально, но я не уверен в его сложности во время выполнения.Я считаю, что это O (n), так как первый цикл O (n), а два внутренних цикла O (2n), но опять же я не уверен.

int[] arr = {0, -3, 5, -4, -2, 3, 1, 0};

for(int num = 0; num < arr.length; num++){
    int sumLeft= 0;
    int sumRight = 0;
    for(int i = 0; i<num; i++){
        sumLeft= sumLeft + arr[i];
    }
    for(int i = num + 1; i < arr.length;i++){
        sumRight= sumRight + arr[i];
    }
    if(sumLeft==sumRight){
        System.out.println(num);
    }
}

Вывод:

0
3
7

Answer 1

Мы можем сделать две вещи:

• Мы можем дать вам ответ, и этот ответ будет O(N^2).

• Мы можемОбъясните, как это сделать для себя.

Способ сделать это - посчитать операции.

Когда я говорю «считать», я нев буквальном смысле.На самом деле я имею в виду, что вам нужно разработать алгебраическую формулу для того, сколько раз показательная операция выполняется.

Итак, в вашем примере я бы назвал эти два утверждения наиболее важными:

      sumLeft= sumLeft + arr[i];

      sumRight= sumRight + arr[i];

(Почему я выбрал эти утверждения? Интуиция / опыт! * педантичный способ сделать это - подсчитать все операций. Но с опытом вы можете выбрать важные ... а остальные не имеют значения.)

Итактеперь для формул:

1. За одну итерацию внешнего цикла первый оператор выполняется из 0 to num-1;то есть num раз.

2. За одну итерацию внешнего цикла второй оператор выполняется из num+1 to array.length - 1;то есть array.length - num - 1 раз.

3. Таким образом, за одну итерацию внешнего цикла два оператора выполняются num + array.length - num - 1 раз, что сокращается до array.length - 1 раз.

4. Но внешний цикл запускается array.length раз.Таким образом, два оператора выполняются array.length x (array.length - 1) раз.

Наконец, по определению Big Oh, array.length x (array.length - 1) находится в классе сложности O(N^2), где N - массивразмер.

Answer 2

это O (n ^ 2)

for(int num = 0; num < arr.length; num++){
    int sumLeft= 0;
    int sumRight = 0;
    for(int i = 0; i<num; i++){// <------------- 1 ~ n
    //https://en.wikipedia.org/wiki/1_%2B_2_%2B_3_%2B_4_%2B_%E2%8B%AF
        sumLeft= sumLeft + arr[i];
    }
    for(int i = num + 1; i < arr.length;i++){
        sumRight= sumRight + arr[i];
    }
    if(sumLeft==sumRight){
        System.out.println(num);
    }
}