Как я могу вычислить среднюю стоимость для этого решения проблемы уникальности элемента?

Question

В книге Введение в разработку и анализ алгоритмов предлагается следующее решение проблемы уникальности элемента:

ALGORITHM UniqueElements(A[0 .. n-1])
// Determines whether all the elements in a given array are distinct
// Input: An array A[0 .. n-1]
// Output: Returns "true" if all the elements in A are distinct
//         and false otherwise.
for i := 0 to n - 2 do
   for j := i + 1 to n - 1 do
      if A[i] = A[j] return false
return true

Как я могу вычислить среднюю стоимость (то есть количество сравнений для данного n) для этого алгоритма? Что является разумным предположением относительно ввода?

Answer 1

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

Это означает, что ваш средний случай равен вашему наихудшему случаю: вам придется сканировать каждый элемент в массиве, чтобы убедиться, что каждый из них отличается. Тогда число сравнений равно n * (n - 1) / 2 или сумме 1 ... n.

Answer 2

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

2 3 4 5 ... 1 1

Или когда массив содержит только отдельные элементы.

Наилучший случай, когда массив начинается с двух повторяющихся элементов, например:

1 1 ...

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

2 3 4 1 ... 1

Это будет (ближе к) O (n).

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

Answer 3

Если вам нужно точное значение для заданной длины ввода, тогда это сработает (хотя это излишне):

ALGORITHM complexity_counter_of_UniqueElements(A[0 .. n-1]) 
// Determines whether all the elements in a given array are distinct 
// Input: An array A[0 .. n-1] 
// Output: Returns "true" if all the elements in A are distinct 
//         and false otherwise. 
counter acc = 0;
for i := 0 to n - 2 do 
   for j := i + 1 to n - 1 do 
      //if A[i] = A[j] return false 
      acc := 1 + acc
return acc

Легко видеть, что этот алгоритм O (n n), хотя, вероятно, это то, что вас интересует. Алгоритм сравнивает каждый элемент по каждому другому элементу. Если вы создали таблицу с результатами этой таблицы, таблица должна быть как минимум ((n n) / 2), чтобы содержать все результаты.

редактирование: Теперь я понимаю, что вы на самом деле спрашивали.

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

Предполагая случайное распределение, вероятность того, что любые два случайных A [x] == A [y], где x! = Y, будет 1,0 / (количество возможных значений элемента).

P(n)
total_chance := 0.0
for i:= 0 to n - 2 do
   for j := i + 1 to n - 1 do
      this_chance := 1.0/(number_of_possible_values_of_element)
      total_chance :=  total_chance + ((1-total_chance)*this_chance)
      // This should be the the probability of the newly compared pair being equal weighted
      // to account for the chance that it actually mattered (ie, hadn't found a match earlier)
return total_chance

O ((1-P (n)) n n), но P (n) <= 1, поэтому оно меньше, чем n * n </p>

Answer 4

Поскольку вы выполняете вложенные операции дважды по массиву, наихудшая стоимость должна составлять O (n²) ..

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

N-1 + (N-2) + (N-3) + (N-4) + (N-5) + .... + 1

сравнений, поэтому точная средняя стоимость будет N*(N-1) / 2

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

Это означает, что элемент A[i] имеет вероятность 1/n быть точно указанным значением. Исходя из этого вы можете сделать ваши соображения:

• прежде всего вы выбираете любой элемент массива A[i]. Какова вероятность наличия A[i] == A[i+1]? Это 1/n², так как оба элемента должны быть случайными.
• какова вероятность наличия A[i] == A[i+2]? У вас есть 1/n * (n-1/n) * 1/n, потому что у вас есть соответственно указанный элемент, все, кроме указанного, и тот же указанный элемент
• Вы можете расширить аргументацию для любого элемента A[k] с помощью k>i, затем вы добавите все вероятности, и вы получите среднюю вероятность наличия двух уникальных элементов в массиве, начиная с указанного.
• вы продлеваете вещь дальше, учитывая, что вы можете начать с любого A[i] с i = 0..l-1. Конечно, у каждого различного i будут разные вероятности, потому что массив будет короче с увеличением i.

ПРИМЕЧАНИЕ : n - это количество различных элементов, которые можно вставить в массив, а не его длина.

После этого вы можете легко оценить среднюю стоимость сравнения.