Временная сложность пар в двойном цикле массива

Question

Я знаю, что следующее: O(n^2),

int count = 0;
for(int i = 0; i<array.length(); i++) {
   for(int j = i+1; j<array.length(); j++) {
       if(array[i] == array[j]) {
           count = count + 1;
       }
   }
}

Но, если что-то вроде count = count + 1; быть принятым во внимание?Для прогнозирования или составления сложного уравнения времени, или с использованием системы счисления,

n + n-1 + n-2 + n-3 + (…) + 1

Answer 1

Это хорошо известная задача «Проверка для дубликатов», и вы можете найти его, например, в TIM Growgarden - Algorittms Blighted_ Часть 1_ Основы - (2017) 42 страница. Позвольте мне сказать, что, как здесь, в книге, принимая последний индекс «i» как $ n= $ "Array.length ()" не имеет смысла, потому что тогда индекс " J «Убегает из границ. Но это не влияет на наш счет.

Как всегда главное - выбрать операцию для подсчета - вот его «счетчик= счет + 1». Очевидно, лучший случай, то есть. Наименее количество операций, является $ 0 $ . И в худшем случае, т. Е. Максимальное количество операций, является сумма (я правильно его соответственно принимаю индекс «i» UP $ N-1 $ ) «Математический контейнер»> $ T (N)= 1 + 2 + \ CDOTS + (N-1)=FRAC {N (N-1)} {2} $ (рассмотрим случай $ n \ geqslant 2 $ ).

Теперь, потому что $ \ frac {n (n - 1)} {2} \ leqslant \ frac {n \ cdot 2n} {2}= n ^ 2 $ , легко сделать вывод, что худшее дело $ t (n) \ in o (n ^ 2) $ .

Answer 2

Временная сложность алгоритма зависит от модели вычислений.Алгоритмы обычно анализируются в оперативной памяти, в которой выполняются базовые операции с машинными словами (такие как присвоение, арифметика и сравнение). $O(1)$.Машинное слово имеет длину $O(\log n)$, где $n$ это размер входных данных.

В вашем случае размер входных данных составляет не менее $n$ (определяется как длина array), и так далее count умещается в одном машинном слове.Каждая из основных операций в алгоритме стоит $O(1)$, и таким образом , общая временная сложность равна $\Тета(n^2)$, поскольку алгоритм выполняет такое количество основных операций.