Проверьте, есть ли в массиве дублированный анализ времени нахождения

Question

Из моего учебника у нас есть алгоритм, который проверяет, есть ли дубликат в массиве, как только дубликат в массиве найден, метод заканчивается (это наивный подход).

Меня спрашиваютчтобы найти сложность с большим Ω в худшем случае.

В этом примере наихудший случай будет иметь место, когда искомые дубликаты находятся рядом в конце или в дубликатах нетмассив.

Меня больше смущает время выполнения в каждой строке.

Например, в коде, который я разместил, первый цикл for будет выполняться (n-1) раз, когда мы имеем9 входов.

Сколько раз в n будет работать второй цикл for в худшем случае? В этом случае он будет проверяться 36 раз.

Я знаю, что наихудшим случаем в сложности Big O будет (n ^ 2). Я знаю, что Big O означает, что f (n) должно максимально достигать (<=) g (n). Я знаю, что Big Ω означает, что f (n) должно как минимум достигать (> =) g (n).

public class test2{
    public static void main(String[] args){
        int[] arrayint = new int[]{5,2,3,7,1,9,6,4,4};

        for(int i = 0; i<arrayint.length-1; i++){ 
            for(int j = i+1; j<arrayint.length;j++){
                if(arrayint[i] == arrayint[j]){
                    System.out.println("duplicate found at " + i + " and " +  j);
                    System.exit(0);
                }
            }
        }
    }
}

Answer 1

Я знаю, что наихудший случай сложности Big O был бы (n ^ 2). Я знаю, что Big O означает, что f (n) должно максимально достигать (<=) g (n). Я знаю, что Большое Ω означает, что f (n) должно, по крайней мере, достигать (> =) g (n).

На самом деле, большое О означает, что f(n) (для достаточно больших входов) не должно достигатьc1 * g(n) - для некоторой константы c1.

Аналогично, для больших омега (Ω), f (n) должно быть больше, чем c2 * g(n) (опять же, для достаточно больших входов).

Это означает, что хорошо иметь один и тот же g(n) как для большого O, так и для большого омега (Ω), потому что вы можете иметь:

c2 * g(n) <= f(n) <= c1 * g(n)

Когда это происходит, мы говорим, что f (n) находится вӨ(g(n)), что означает, что асимптотическая граница жесткая. Вы можете найти больше информации в этой теме о большой тэте (Ө)

В вашем случае наихудший случай - когда в массиве нет дубликатов. В этом случае как O(n^2), так и Ω(n^2), что дает жесткую границу Ө(n^2).

. В качестве дополнительного примечания эта проблема называется проблемой отличимости элементов , котораяинтересен тем, что сама проблема (не алгоритм) имеет несколько асимптотических границ, основанных на используемой нами модели вычислений.

Answer 2

Если i=0, то j будет варьироваться от 1 до 8. Внутренний цикл выполняется 8 раз.

Когда i=1, внутренний цикл выполняется 7 раз (j = от 2 до 8)

Как правило, когда i=x, внутренний цикл выполняется n-i-1 раз.

Если вы суммируете все итерации, вы получите (n*(n-1))/2 итераций. Так что для 9 предметов это (9*(9-1))/2) или 36 раз.