Этот алгоритм не имеет квадратичного времени выполнения, верно?

Question

У меня недавно было интервью, и мне дали небольшую проблему, которую я должен был написать.

Проблема была в основном найти дубликаты в массиве длины n, используя постоянное пространство в O (n). Каждый элемент находится в диапазоне 1- (n-1) и гарантированно будет дубликатом. Вот что я придумал:

public int findDuplicate(int[] vals) {
    int indexSum=0;
    int valSum=0;   
    for (int i=0; i< vals.length; i++) {
         indexSum += i;
         valSum += vals[i];
    }
    return valSum - indexSum;
}

Затем мы приступили к обсуждению времени выполнения этого алгоритма. Сумма рядов от 0 -> n = (n ^ 2 + n) / 2, которая является квадратичной. Однако разве алгоритм не O (n) время? Количество операций ограничено длиной массива, верно?

Чего мне не хватает? Этот алгоритм O (n ^ 2)?

Answer 1

Тот факт, что сумма целых чисел от 0 до n равна O(n^2), здесь не имеет значения.

Да, вы проходите через цикл ровно O(n) раз.

Большой вопрос, какой порядок сложности вы предполагаете при добавлении?

Если O(1), то да, это линейно. Большинство людей предположит, что сложение равно O(1).

Но что, если сложение на самом деле O(b) (b - это биты, а в нашем случае b = log n)? Если вы предполагаете это, то этот алгоритм на самом деле O(n * log n) (добавляя n чисел, для представления каждого из которых необходимо log n бит).

Опять же, большинство людей считают, что сложение равно O(1).

Answer 2

Алгоритмы исследователей стандартизированы для модели RAM с удельной стоимостью , где слова - это тэта (log n) биты, а операции со словами - это тета (1) время. Альтернативная модель, в которой операции со словами - это тэта (log n) время, больше не используется, потому что смешно иметь ОЗУ, которое не может распознавать палиндромы за линейное время .

Ваш алгоритм четко выполняется во времени O (n) и дополнительном пространстве O (1), так как условием для единицы по умолчанию является слово. Ваш интервьюер, возможно, беспокоился о переполнении, но ваш алгоритм работает нормально, если сложение и вычитание выполняются по модулю любого числа M ≥ n, как в случае с дополнением до двух.

tl; dr Какая бы ни была проблема вашего интервьюера, она мнимая или коренится в неправильном понимании условностей теоретической информатики.

Answer 3

Вы работаете с каждым на n ячейках по одному разу. Линейное время.

Answer 4

Да, алгоритм является линейным *.Результат valSum не влияет на время выполнения.Скажем так: функция

int f(int[] vals) {
   return vals.length * vals.length;
}

дает n ² в 1 умножении.Очевидно, это не означает, что f - это O (n ² );)

^{(*: при допущении, что O (1))}

Answer 5

Сумма i от i = 0 до n равна n * (n + 1) / 2, которая ограничена n^2, но это не имеет никакого отношения ко времени выполнения ... это просто замкнутая форма суммирования .

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

Надеюсь, это поможет.
Христо