Разница в использовании и для решения общего количества возможных треугольников

Question

Я столкнулся с этой проблемой в Codility.Смотрите эту ссылку .Мне удалось решить эту проблему.Тем не менее, это вызывает у меня некоторые вопросы.

Вот код, использующий три for.

public int solution(int[] A) {
    Arrays.sort(A);
    int k, count = 0;
    for (int i = 0; i < A.length - 2; i++){
        for (int j = i + 1; j < A.length - 1; j++){
            for (k = j + 1; k < A.length; k++){
                if (A[i] + A[j] > A[k]) break;
            count += k - j - 1;
        }
    }
    return count;
}

Это код, использующий while во внутренних for.

public int solution(int[] A) {
    // write your code in Java SE 8
    Arrays.sort(A);
    int k, count = 0;
    for (int i = 0; i < A.length - 2; i++){
        k = i + 2;
        for (int j = i + 1; j < A.length; j++){
            while (k < A.length && A[i] + A[j] > A[k]) {
                k++;
            }
            count += k - j - 1;
        }
    }
    return count;
}

Первое решение, приведенное выше, не дает мне идеального результата в Codility, потому что для его компиляции в большом тестовом примере требуется так много времени.Однако во втором решении, использующем while, я получаю отличную оценку.Почему это так, хотя я поставил проверку треугольников в обоих этих кодах выше?for и while как-то связаны с ними?

Я также читал о сложности времени из второго решения.Вот ссылка .Существует разница в том, как инициализируется переменная k.Оказывает ли эта разница огромное влияние на производительность этих двух кодов?

Я пытаюсь выяснить, в чем именно разница между этими двумя кодами.

Answer 1

for loop и while loop не имеют ничего общего с этими решениями.Фактически, мы можем изменить второе решение, чтобы сделать цикл while как цикл for, как показано ниже:

 public int solution(int[] A) {
        Arrays.sort(A);
        int k, count = 0;
        for (int i = 0; i < A.length - 2; i++) {
            k = i + 2;
            for (int j = i + 1; j < A.length; j++) {
                for( ; k < A.length; k++) {
                    if ( (A[i] + A[j]) <= A[k]) break;
                }
                count += k - j - 1;
            }
        }
        return count;
    }

На самом деле, основная логика двух ваших решений совершенно различна.

В первом решении:
Мы фиксируем все возможные тройки, используя три цикла for, и разрывая третий цикл, как только сумма первых двух наименьших пар длины будет меньше или равнаэто третьего, то есть это должно быть "if (A[i] + A[j] <= A[k]) break;".Таким образом, общая сложность времени будет O(n^3).

Во втором решении:
Мы только фиксируем два for loops и выполняем вычисления.Цикл while в вашем коде запускается только один раз для каждого for loop с использованием i.Так как массив был отсортирован один раз, идея этого решения состоит в том, что если мы объединяем два значения, используя первые два for loops, а сумма значений в индексах i и j равна sum, то есть sum = A[i] + A[j], и еслион встречает значение по индексу k, которое больше или равно sum, чем для следующей пары i и j + 1, третий индекс будет определенно больше, чем предыдущий k, поскольку значение по индексу j + 1больше значения в индексе j, то есть A[j] <= A[j + 1].Таким образом, третий индекс должен быть точно в правой части, чем предыдущий k.Таким образом, общая сложность второго решения составляет O(n^2).

Answer 2

Во втором решении k никогда не уменьшится во втором слое цикла.

Таким образом, временная сложность первого решения равна O (n ^ 3), тогда как временная сложность второго решения равна O (n^ 2),