Сложность алгоритма, который повторяется на основе максимального числа в массиве? - PullRequest
Новая
       2

Сложность алгоритма, который повторяется на основе максимального числа в массиве?

0 голосов
/ 13 февраля 2020

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

Дело в том, что я нашел странный способ сделать это, но мы не можем по-настоящему обдумать сложность, потому что думаем, что она может не иметь формальной сложности?

Краткое объяснение проблема заключается в следующем:

У вас есть массив (возможно, не упорядоченный) целых чисел, все положительные и больше 0.

Ваша задача - сообщить мне первое целое число, которое отсутствует в массив, например:

[1, 4, 5,3, 2, 6, 10] ==> Ответ 7

Мой забавный способ сделать это было:

Вы перебираете массив один раз и помещаете все значения в HashMap, сохраняя максимальное значение в массиве в отдельной переменной.

После этого вы создаете для l oop, что идет от 1 до максимального значения массива.

Затем вы проверяете, если для l oop индекс существует в хэш-карте, если его нет, то вы нашли свой ответ.

Дело в том, что это будет O (n), но для l oop мне все равно немного .. Это O (n)? Неправильно говорить это O (n).

Представьте себе этот псевдокод:

let numArray = {1, 2, 3, 1000}; 

for i=1 TO max(numArray){
     print "Hello there buddy"
}

Какова будет сложность этого? Есть ли формальная сложность?

Насколько я понимаю, утверждение, что оно имеет сложность, на самом деле не следует цели Big O Notation, поскольку его целью является оценка времени, которое потребуется для выполнения некоторого кода, имеет РАЗМЕР входные данные меняются, и здесь не имеет значения размер входных данных, просто значение максимального числа ... Если массив состоит из 3 элементов, а максимальное значение равно 1 миллиарду, все равно потребуется 1 миллиард итераций ...

Итак, есть ли для этого специальные обозначения c?

Как бы вы описали эту проблему?

1 Ответ

0 голосов
/ 13 февраля 2020

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

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

предположим, 

a = [1, 4, 5,3, 2, 6, 10]
for i in 0->n:
  if (a[i] < n)
    a[a[i]] = -a[a[i]];

for i in 0->n:
  if (a[i] > 0)
    print (i);

По сути, идея состоит в том, чтобы пометить посещенный индекс, изменив его знак на -ve. При повторной итерации первым найденным индексом положительного элемента будет отсутствующий элемент.

...