Время и сложность целочисленного массива

Question

Я работаю над заданием и не получаю ответа на некоторые вопросы.

меня спросили:

Вход: массив A длины N, которая может содержать только целые числа от 1 до N

Выход: TRUE - А содержит дубликат, FALSE - в противном случае.

Я создал класс, который передает мои тестовые примеры.

public class ArrayOfIntegers { 


public boolean isArrayContainsDuplicates(int [] intArray){ 

    int arraySize = intArray.length; 

    long expectedOutPut = arraySize*(arraySize+1)/2; 

    long actualOutput = 0; 

    for(int i =0 ; i< arraySize; i++){ 

     actualOutput = actualOutput + intArray[i]; 

    } 

    if(expectedOutPut == actualOutput) 
     return false; 

    return true; 
} 

} 

Теперь дальнейшие вопросы по этому

1. Можно ли дать ответ, а не уничтожить входной массив A?

   Я не уничтожаю массив. Так что я сделал правильно?

2. Анализ временной и пространственной сложности вашего алгоритма?

   Так что мне нужно написать что-нибудь о цикле for, чтобы как только я нахожу дублирующие элементы, я должен сломать цикл. Честно говоря, я не совсем понимаю концепцию сложности времени и пространства.

3. Возможно ли использовать O (n) для использования как времени, так и пространства?

   Это должно быть Нет, так как n может быть любым числом. Опять же, я не очень понимаю о O (n).

Благодаря

Answer 1

public boolean hasDuplicates(int[] arr) { 
    boolean found = false; 
    for (int i = 1 ; i <= arr.length ; i++) { 
     for (int a : arr) 
      if (a == i) found = true; 
     if (! found) return true; 
    } 
    return false; 
} 

Я считаю, что этот метод будет работать (как и в настоящее время нет). Это O (n^2).

Я уверен, что невозможно достичь O (n) для времени и пространства, так как потребуются две вложенные петли, тем самым увеличивая сложность метода.

Редактировать

я был неправ (иногда это хорошо, чтобы признать это), это O (п):

public boolean hasDuplicates(int[] arr) { 
    int[] newarr = new int[arr.length]; 
    for (int a : arr) newarr[a - 1]++; 
    for (int a : newarr) if (a != 1) return true; 
    return false; 
} 

1. Да, вводный массив не разрушается.
2. Метод непосредственно выше - O (n) (под этим я подразумеваю, что его требования к времени выполнения и пространства будут линейно расти с длиной массива аргументов).
3. Да, см. Выше.

Answer 2

Как намеков:

1. Да, можно дать ответ, а не уничтожить массив. Например, приведен код ^*.

2. Сложность времени может быть рассмотрена как «сколько значимых операций выполняет этот алгоритм?» Поскольку ваш цикл идет от 0 до N, как минимум, вы выполняете O (N) работу.

   Сложность пространства можно рассматривать как «сколько пространства я использую во время этого алгоритма?» Вы не делаете никаких дополнительных массивов, поэтому ваша пространственная сложность имеет порядок O (N).

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

^{*: Ваш код также не находит все дубликаты в массиве. Вы можете вернуться к этому.}

Answer 3

Возможно ли предоставить ответ и НЕ уничтожить входной массив A?

Да.Например, если вас не волнует время, которое требуется, вы можете циклически перебирать массив один раз для каждого возможного числа и проверять, видите ли вы его ровно один раз (если нет, должен быть дубликат). Это будет O (N^2).

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

Анализ временной и пространственной сложности вашего алгоритма?

Ваш алгоритм работает в O (n), выполняя только один проход по входному массиву и не требует дополнительного пространства. Однако это не работает.

Возможно ли использовать O (n) как время, так и пространство?

Да.

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

Так что мне нужно написать что-нибудь о цикле for, чтобы как только я нахожу дубликаты элементов, я должен сломать цикл.

Нет. Соображения сложности всегда относятся к наихудшему случаю (или иногда к среднему случаю). В худшем случае вы не можете выйти из цикла. В среднем случае вы можете вырваться после половины цикла. В любом случае, хотя важно, чтобы кто-то ожидал реальной реализации для завершения вычисления, это не влияет на масштабируемость (сложность, когда N растет бесконечно). Не учитываются постоянные смещения и множители (например, 50% для раннего выхода).

Answer 4

1) Это не потребует больших усилий, и оставляет массив нетронутым:

public boolean isArrayContainsDuplicates(int [] intArray){ 
    int expectedOutPut = (intArray.length*(intArray.length+1))/2; 
    int actualOutput = 0; 
    for(int i =0 ; i < intArray.length; i++){ 
    if(intArray[i]>intArray.length)return true; 
    actualOutput += intArray[i]; 
    } 
    return expectedOutPut == actualOutput ? false: true; 
} 

2) Это потребует прикасаясь изменяющееся количество элементов в массиве. Наилучший случай, он попадает в первый элемент, который будет O (1), средний случай - это попадание в среднее O (log n), и худший случай - он проходит весь путь и возвращает false O (n).

O (1) относится к ряду операций, которые не относятся к общему количеству элементов. В этом случае первый элемент будет единственным, который имеет этот случай.

O (log n) - log является предельным фактором, который может быть действительным числом от 0 до 1. Таким образом, умножение на log приведет к меньшему числу. Следовательно, O (log n) относится к требуемому количеству операций, которые меньше количества элементов.

O (n) - Это когда требуется количество операций, равное количеству элементов.

Все они обозначены большими знаками на требуемое время.

В этом алгоритме используется память, которая увеличивается с увеличением n. Однако он не будет расти линейно, а вместо этого будет частью размера n, поэтому его пространственный Big-O равен O (log n).

3) Да, это возможно - однако это возможно только в лучших сценариях.

Answer 5

Возможно, добавив все элементы в hashset = O (n), а затем сравните количество значений в хэш-наборе с размером массива = O (1). Если они не равны, то есть дубликаты.

Создание хешета также будет занимать меньше места в среднем, чем создание целочисленного массива для подсчета каждого элемента. Это также улучшение от 2n до n, хотя это не влияет на big-O.