Algorytmy: Jak sumować O (n) i O (nlog (n)) razem?

22

Mam następujący algorytm, który wyszukuje duplikaty i usuwa je:

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;
}

Usiłuję znaleźć najgorszą złożoność tego przypadku. Wiem, że jest to połączenie nlog(n), a w mojej pętli for iteruję cały zestaw danych, więc byłoby to liczone jako n. Nie jestem jednak pewien, co zrobić z tymi liczbami. Czy powinienem je po prostu zsumować? Gdybym to zrobił, jak miałbym to zrobić?

algorithms algorithm-analysis big-o chopper draw lion4
źródło
1
Uwaga dodatkowa: możesz użyć tabeli skrótów, aby to zrobić w O (n) w zależności od wymagań pamięci.
corsiKa,

Odpowiedzi:

67 
O(n) + O(n log(n)) = O(n log(n))

Dla złożoności Big O wszystko, na czym ci zależy, to dominujący termin. n log(n)dominuje, nwięc to jedyny termin, na którym ci zależy.

Justin Cave
źródło
4
Innym sposobem myślenia o tym jest wyobrażenie sobie, że twoje przetwarzanie O (n) było tak naprawdę O (n log n), tak jakbyś zrobił dwa niezależne rodzaje. Wtedy miałbyś 2 * O (n log n). Ale stałe znikają, więc wracasz do O (n log n).
Jonathan Eunice
4
@Jathanathan Chociaż działa to w praktyce, jest bardzo prawdą, że O (n) nie jest równe O (n log (n)), więc nie zalecałbym regularnego używania tego.
Aza
17
@Emrakul tak naprawdę myślę, że rozumowanie jest teoretycznie solidne i praktyczne. O (n) jest właściwym podzbiorem O (n log (n)). Więc jeśli f (n) należy do O (n), to również należy do O (n log (n)).
emory
17
Należy zauważyć, że kiedy mówimy f(n) is O(g(n)), tak naprawdę mówimy, że jest to funkcja f is a member of the set of functions that grows at the rate of at most g(n) over the long term. Oznacza to, że wszyscy członkowie O(n)są również członkami O(n*log(n)). +W wyrażeniach lubią O(f(n)) + O(g(n))rzeczywiście odnoszą się do ustawionej Unii (co naprawdę jesteś pedantyczny, naprawdę powinny korzystać ∪).
Lie Ryan,
3
@LieRyan Początkowo nie jest ustawiona unii, ale zestaw suma: A + B = { a + b | a in A, b in B }. Zdarza się, że dla zbiorów postaci O(g(n))jest to to samo, co zbiór jedności, ponieważ jeden ze zbiorów jest zawsze podzbiorem drugiego i oba są niezmienne w stosunku do sum (tj. A + A = A). (Ups, Nate napisał zasadniczo to samo).
Paŭlo Ebermann
56

Prześledźmy naszą drogę i pamiętajmy definicję O. Ten, którego zamierzam użyć, to limit w nieskończoności.

Masz rację, twierdząc, że wykonać dwie operacje z odpowiednimi asymptotyczne granice O(n)i O(nlog(n))ale łącząc je w jeden związany nie jest tak proste jak dodanie dwie funkcje. Wiesz, że twoja funkcja zajmuje przynajmniej O(n)czas, a także przynajmniej O(nlog(n))czas. Tak naprawdę klasa złożoności dla funkcji jest sumą O(n)i O(nlog(n))ale O(nlog(n))jest rozszerzeniem O(n)tak naprawdę jest to po prostu O(nlog(n)).

davidk01
źródło
12
+1 to powinna być odpowiedź. Dokładniej opisuje odpowiedź przy użyciu terminów compsci.
5

Jeśli zamierzasz ustawić go z długim czasem, wyglądałoby to mniej więcej tak:

Załóżmy, że całkowity czas to: an + bn log (n), gdzie aib są stałymi (ignorując terminy niższego rzędu).

Gdy n idzie do nieskończoności (an + bn log (n)) / n log (n) -> a / log (n) + b -> b

Zatem całkowity czas wynosi O (bn log (n)) = O (n log (n)).

richardb
źródło
2

Zacznij od definicji O ():

O (n log n) oznacza „mniej niż C n log n, jeśli n jest duże”.

O (n) oznacza „mniej niż D n, jeśli n jest duże”.

Jeśli dodasz oba, wynik będzie mniejszy niż C n log n + D n <C n log n + D n log n <(C + D) n log n = O (n log n).

Ogólnie, jeśli f (n)> C g (n) dla dużego n, a niektóre C> 0, to O (f (n)) + O (g (n)) = O (f (n)). A po wykonaniu kilku przypadków przy użyciu definicji O () będziesz wiedział, co możesz, a czego nie możesz zrobić.

gnasher729
źródło
1

Duża notacja O jest zdefiniowana jako zbiór:

wprowadź opis zdjęcia tutaj

wprowadź opis zdjęcia tutajZawiera więc wszystkie funkcje, które - zaczynając od jakiegoś dużego punktu wprowadź opis zdjęcia tutaj- zawsze są mniejsze niż g.

Teraz, gdy masz funkcję, która jest włączona, wprowadź opis zdjęcia tutaja następnie uruchom inną, która zwiększa się wolniej niż g, z pewnością rośnie wolniej niż 2 g. Wykonanie czegokolwiek wolniejszego niż g nie zmieni klasy złożoności.

Bardziej formalnie:

f, h \ in \ mathcal {O} (g) \ Rightarrow (f + h) \ in \ mathcal {O} (g)

Możesz to łatwo udowodnić.

TL; DR

To jest nadal n log (n)

Martin Thoma
źródło