Временная сложность Arrays.deepEquals () в Java - PullRequest
Новая
       81

Временная сложность Arrays.deepEquals () в Java

1 голос
/ 30 октября 2019

Я пытаюсь выяснить сложность времени для метода java.util.Arrays deepEquals ().

Я мог бы понять из исходного кода, что метод equals () выполняется за O (n) времени, но на самом деле не совсем ясно, насколько сложно вывести временную сложность из метода deepEquals (). Он выполняется в цикле, но также вызывает метод deepEquals0, который должен рекурсивно проверять равные элементы? Так что же здесь будет в худшем случае?

Вот фрагмент кода, который был взят из класса java.util.Arrays: 

public static boolean deepEquals(Object[] a1, Object[] a2) {
    if (a1 == a2)
        return true;
    if (a1 == null || a2==null)
        return false;
    int length = a1.length;
    if (a2.length != length)
        return false;

    for (int i = 0; i < length; i++) {
        Object e1 = a1[i];
        Object e2 = a2[i];

        if (e1 == e2)
            continue;
        if (e1 == null)
            return false;

        // Figure out whether the two elements are equal
        boolean eq = deepEquals0(e1, e2);

        if (!eq)
            return false;
    }
    return true;
}

static boolean deepEquals0(Object e1, Object e2) {
    assert e1 != null;
    boolean eq;
    if (e1 instanceof Object[] && e2 instanceof Object[])
        eq = deepEquals ((Object[]) e1, (Object[]) e2);
    else if (e1 instanceof byte[] && e2 instanceof byte[])
        eq = equals((byte[]) e1, (byte[]) e2);
    else if (e1 instanceof short[] && e2 instanceof short[])
        eq = equals((short[]) e1, (short[]) e2);
    else if (e1 instanceof int[] && e2 instanceof int[])
        eq = equals((int[]) e1, (int[]) e2);
    else if (e1 instanceof long[] && e2 instanceof long[])
        eq = equals((long[]) e1, (long[]) e2);
    else if (e1 instanceof char[] && e2 instanceof char[])
        eq = equals((char[]) e1, (char[]) e2);
    else if (e1 instanceof float[] && e2 instanceof float[])
        eq = equals((float[]) e1, (float[]) e2);
    else if (e1 instanceof double[] && e2 instanceof double[])
        eq = equals((double[]) e1, (double[]) e2);
    else if (e1 instanceof boolean[] && e2 instanceof boolean[])
        eq = equals((boolean[]) e1, (boolean[]) e2);
    else
        eq = e1.equals(e2);
    return eq;
}

Заранее спасибо.

Ответы [ 2 ]

3 голосов
/ 30 октября 2019

Метод выполняется linear для общего количества элементов . Если мы обозначим это как n, это будет O(n).

Звучит лучше, чем есть, представьте, что у вас есть вложенный массив int[][][], например: 

{                     // int[][][]
    { 1, 2, 3 },      // int[]
    { 4, 5 },         // int[]
    {                 // int[][]
        { 6, 7, 8 },  // int[]
        { 9 }         // int[]
    }
}

Тогда мыиметь 9 int значений в общей сложности. Под n я подразумевал те 9 элементы, а не 4 для массивов внешней структуры. На этом он работает линейно n.

Опять же, я не говорю о outer.length (то есть 4), я говорю о фактическом количестве элементов, если вы полностью следите за всей структурой, если вы сгладите это. На самом деле невозможно выразить сложность в терминах outer.length, поскольку она совершенно не связана. Небольшой пример, демонстрирующий это: 

{
    {
        { 1, 2, 3, 4, ..., 1_000_000 }
    }
}

Здесь input.length - это просто 1, но фактическое количество элементов довольно велико. Вы видите, это не связано.

Причина, по которой он снова вызывает себя, состоит в том, что, представьте, что у вас есть Object[][][][] (4 измерения), тогда вы также должны проверить all из этих размеров. Так что он действительно проверяет все элементы.

2 голосов
/ 30 октября 2019

Я немного отступлю от идеи «линейного числа объектов», потому что на самом деле не имеет значения, является ли входной массив массивом Object или массивом Object[] или чем-то ещеостальное. Что действительно важно, так это то, как вы определяете свою запись в формате big-O. А именно: если вы хотите связать биг-О вашего алгоритма с размером вашего входа, вы должны знать, какой «размер вашего входа» равен . Вы должны определить n в O(n). Например:

  1. Ваш ввод MyObject[] из size = n, где MyObject имеет метод equals, который требует k работы, где k - константа,Что такое время выполнения deepEquals()? Ну, вы делаете k работу, n раз, так что вы получаете O(n*k), выбрасываете константу, чтобы получить O(n). Отлично!

  2. Далее вы вводите MyObject[][], где массив верхнего уровня имеет размер n, а вложенные массивы имеют размер j, константу. Что такое время выполнения? n подмассивы, каждая длиной j, где каждый MyObject занимает k работу. O(n*j*k), выбросить константы, чтобы получить O(n) снова. ПРИМЕЧАНИЕ , что наш вход увеличился в j раз, но big-O не изменился, потому что мы предполагаем, что j является постоянным, то есть вопрос, который мы задаем, - как изменяется время выполнения с изменениями вдлина массива верхнего уровня ".

  3. Что, если вместо этого мы спросим" как меняется время выполнения с изменениями длины массива верхнего уровня и изменениями длинывложенных массивов? Пусть наш вход будет размером n, с размером вложенных массивов m, который не является константным . Теперь мы получаем O(n*m*k), выбрасываем константу k, чтобы получить O(n*m). Если мы требуем, чтобы наша входная матрица (вложенный массив) была квадратной, т.е. n = m, наше время выполнения теперь равно O(n^2).

Что ?????

В # 2 n - длина массива верхнего уровня. Мы предпочитаем игнорировать тот факт, что длина подмассивов может варьироваться.

В # 3мы усвоим этот факт и представим m длину подмассивов, чтобы получить n*m или n^2 при n = m.

Мы можем пойти дальше :

Если метод equals для MyObject не требует k постоянного времени, а вместо этого равен O(p), гдеp - это размер коллекции, содержащейся в MyObject, тогда время выполнения # 3 выше становится O(n*m*p), где n*m - это число MyObject, а p - это размер MyObject '. с коллекцией, и вы можете продолжать делать это вечно .

В результате запись big-O является bound , которая действительна, если вы предполагаете, что некоторыевещи. Основная часть этих допущений (о которых мы не часто думаем) состоит в том, что каждая переменная (переменная, которая действительно может измениться) не в скобках O() не имеет значения, потому что оназатмеваются тем, что являются в скобках. Это означает, что в зависимости от того, намного ли важнее n, чем m, можно сказать, что оба значения # 3 находятся в пределах O(n), а № 3 - в пределах O(n*m) и будут правильными, согласно вашим предположениям.

...