Big Oh for (n log n)

Question

Obecnie studiuję podstawowe algorytmy dla Big Oh. Zastanawiam się, czy ktokolwiek może mi pokazać, jaki kod (n log n) w Javie używałby Big Oh, lub przekierować mnie na dowolną stronę SO, na której istnieje.

Ponieważ jestem dopiero początkującym, mogę sobie tylko wyobrazić kod, zanim go napiszę. Teoretycznie (przynajmniej) powinien zawierać jedną pętlę for, w której mamy coś n razy. Następnie dla dziennika n możemy użyć pętli while. Tak więc pętla jest wykonywana n razy, a pętla while jest wykonywana 2 razy w logu. Przynajmniej tak to sobie wyobrażam w głowie, ale zobaczenie kodu wyjaśni sprawę.

Answer 1

Bardzo popularnym algorytmem O (n log n) jest sortowanie scalone. http://en.wikipedia.org/wiki/Merge_sort na przykład algorytmu i pseudokod. Część log n algorytmu uzyskuje się poprzez podzielenie problemu na mniejsze podproblemy, w których wysokość drzewa rekursji to log n.

Wiele algortihms sortujących ma czas działania O (n log n). Więcej przykładów można znaleźć na stronie http://en.wikipedia.org/wiki/Sorting_algorithm.

Answer 2

http://en.wikipedia.org/wiki/Heapsort

Prostym przykładem jest właśnie tak, jak to opisano - wykonywać n razy jakieś działanie, które ma log (n). Zrównoważone drzewa binarne mają wysokość log (n), więc niektóre algorytmy drzewa będą miały taką złożoność.

Answer 3

int n = 100 
for(int i = 0; i < n; i++) //this loop is executed n times, so O(n) 
{ 
    for(int j = n; j > 0; j/=2) //this loop is executed O(log n) times 
    { 

    } 
} 

Objaśnienie: Zewnętrzna pętla powinna być wolna. Jest wykonywany n razy. Teraz do wewnętrznej pętli. W wewnętrznej pętli po prostu wziąć n i zawsze podzielić go przez 2. więc zadaj sobie pytanie: Ile razy mogę podzielić n przez 2.

Okazuje się, że jest to O (log n). (w rzeczywistości podstawą logu jest 2, ale w notacji Big-Oh opuszczamy bazę, ponieważ dodaje ona tylko niektóre czynniki do naszego logu, który nas nie interesuje).

Wykonuje się pętlę n razy iw tej pętli wykonuje się kolejną pętlę log(n) razy, więc masz O(n) * O(log n) = O(n log n).

Answer 4

Algorytmy o złożoności O(.) obejmującej zwykle log n zwykle obejmują jakąś formę dzielenia i zdobywania.

Na przykład, wlista jest o połowę mniejsza, każda część jest indywidualnie sortowana, a następnie dwie połówki są łączone razem. Każda lista jest o połowę.

Ilekroć praca ma być zmniejszona o połowę lub zmniejszony o jakiś stały współczynnik, zazwyczaj kończy się na składniku log n z O(.).

Pod względem kodu, spójrz na algorytm MergeSort. Ważną cechą typowych implementacji jest to, że jest rekursywna (zauważ, że TopDownSplitMerge wywołuje się dwukrotnie w kodzie podanym w Wikipedii).

Wszystkie dobre standardowe algorytmy sortowania mają złożoność czasową i nie można tego zrobić lepiej w najgorszym przypadku, patrz Comparison Sort.

Aby zobaczyć, jak to wygląda w kodzie Java, wystarczy search! Here's one example.