У меня есть следующий алгоритм, который находит дубликаты и удаляет их:
public static int numDuplicatesB(int[] arr) {
Sort.mergesort(arr);
int numDups = 0;
for (int i = 1; i < arr.length; i++) {
if (arr[i] == arr[i - 1]) {
numDups++;
} }
return numDups;
}
Я пытаюсь найти наихудший случай сложности времени. Я знаю, что mergesort есть nlog(n), и в моем цикле for я выполняю итерацию по всему набору данных, чтобы это считалось n. Я не уверен, что делать с этими числами, хотя. Должен ли я просто сложить их вместе? Если бы я это сделал, как бы я это сделал?
algorithms
algorithm-analysis
big-o
тяпка ничья lion4
источник
источник
Ответы:
Для сложности Big O все, что вас волнует, это доминирующий термин.
n log(n)доминирует,nтак что это единственный термин, который вас волнует.источник
f(n) is O(g(n))мы действительно говорим, что функцияf is a member of the set of functions that grows at the rate of at most g(n) over the long term. Это означает, что все членыO(n)также являются членамиO(n*log(n)).+В таких выражениях , как наO(f(n)) + O(g(n))самом деле относится к множественному объединению (что вы действительно педантичными, вы действительно должны использовать ∪).A + B = { a + b | a in A, b in B }. Бывает, что для наборов формыO(g(n))это то же самое, что и объединение множеств, поскольку один из наборов всегда является подмножеством другого, и оба они инвариантны к суммам (т. Е. A + A = A). (Ой, Нейт действительно написал то же самое).Давайте рассмотрим наш путь и вспомним определение
O. Тот, который я собираюсь использовать, для предела в бесконечности.Вы правы в том , что вы выполнить две операции с соответствующими асимптотические пределы
O(n)и ,O(nlog(n))но их объединения в единую границу не так просто , как добавить две функции. Вы знаете, что ваша функция занимает минимумO(n)времени, а также минимумO(nlog(n))времени. Так на самом деле класс сложности для вашей функции является объединениемO(n)иO(nlog(n))ноO(nlog(n))является надстройкойO(n)так на самом деле это простоO(nlog(n)).источник
Если бы вы собирались изложить это от руки, это выглядело бы примерно так:
Предположим, что общее время: an + bn log (n), где a и b - константы (игнорируя члены более низкого порядка).
Когда n переходит в бесконечность (an + bn log (n)) / n log (n) -> a / log (n) + b -> b
Таким образом, общее время O (bn log (n)) = O (n log (n)).
источник
Начнем с определения O ():
O (n log n) означает «меньше, чем C n log n, если n большое».
O (n) означает «меньше, чем D n, если n большое».
Если вы добавите оба, результат будет меньше C n log n + D n <C n log n + D n log n <(C + D) n log n = O (n log n).
В общем, если f (n)> C g (n) для больших n и некоторого C> 0, то O (f (n)) + O (g (n)) = O (f (n)). И после нескольких случаев использования определения O () вы будете знать, что вы можете и не можете сделать.
источник
Большая нотация O определяется как набор:
Таким образом,
содержит все функции, которые - начиная с некоторой произвольно большой точки 
- всегда меньше, чем g.
Теперь, когда у вас есть функция, которая находится внутри,
а затем выполните другую, которая увеличивается медленнее, чем g, она, безусловно, увеличивается медленнее, чем 2g. Таким образом, выполнение чего-либо более медленного, чем g, не изменит класс сложности.
Более формально:
Вы можете легко доказать это.
TL; DR
Это все еще
источник