Лучшее, худшее и среднее время выполнения функции для проверки дубликатов?

Question

У меня возникли некоторые проблемы с поиском большого O для если заявление в коде ниже:

public static boolean areUnique (int[] ar) 
{ 
    for (int i = 0; i < ar.length-1; i++) // O(n) 
    { 
     for (int j = i+1; j < ar.length-1; j++) // O(n) 
     { 
      if (ar[i] == ar[j]) // O(???) 
       return false; // O(1) 
     } 
    } 

    return true; //O(1) 
} 

Я пытаюсь сделать анализ временной сложности на лучшее, худшее, и средний случай

Спасибо всем за ответ так быстро! Я не уверен, что мои лучшие худшие и средние случаи верны ... Разница должна быть в случае, если это не из-за утверждения if? Но когда я делаю анализ у меня они все в конечном итоге, как O (п)

• Лучший: О (п) * O (п) * [O (1) + O (1)] = О (п)
• Худшие: О (п) * О (п) * [O (1) + O (1) + O (1)] = п
• Средний балл: O (п) * О (п) * [O (1) + O (1) + O (1)] = О (п)

Я делая это право? Мой учебник не очень полезен

Answer 1

само по себе является O (1);

Это связано с тем, что он не принимает во внимание процесс в ALU или CPU, поэтому если (ar [i] == ar [j]) будет в действительности O (6), что переводится в O (1)

Answer 2

Вы можете рассматривать его как O (1).

Независимо от того, что вы считаете, как «один» шаг,

инструкции для проведения [я] == а [у] не зависит от значения п

в этом случае.

Answer 3

Для начала, эта линия

if (ar[i] == ar[j]) 

всегда занимает много времени Θ (1) для выполнения. Он выполняет только постоянную работу (сравнение плюс ветвь), поэтому работа, проделанная здесь, не будет асимптотически способствовать общей продолжительности выполнения.

Учитывая это, мы можем проанализировать поведение наихудшего случая, рассмотрев, что произойдет, если это утверждение всегда ложно. Это означает, что цикл работает как можно дольше. Как вы заметили, поскольку каждый цикл работает O (n) раз, общая работа выполнена в Θ (n) в наихудшем случае.

В лучшем случае, однако, время работы значительно ниже. Представьте себе любой массив, где первые два элемента одинаковы. В этом случае функция прекращается почти мгновенно, когда условие встречается впервые. В этом случае время выполнения составляет Θ (1), поскольку будет выполнено постоянное число операторов.

Среднее значение, однако, здесь не определено. Среднее значение обычно определяется относительно некоторого распределения - среднее по сравнению с чем? - и неясно, что здесь.Если вы предполагаете, что массив состоит из действительно случайных значений int и что int s может принимать любое целочисленное значение (не разумное предположение, но пока оно прекрасное), то вероятность того, что случайно выбранный массив имеет дубликат, равна 0 и мы вернулись в худшем случае (время выполнения Θ (n)). Однако, если значения более ограничены, среда выполнения изменяется. Предположим, что в массиве есть n чисел, а целые числа - от 0 до k - 1 включительно. Учитывая случайный массив, среда выполнения зависит от

• ли есть какие-либо дубликаты или нет, и
• Если есть дубликат, где первое дублируется значение отображается в массиве.

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

Надеюсь, это поможет!