Confused o Big O notacji

Question

Mam dwa pytania:

public static void method1(int[] a, int[] b) { 
    int sum1 = 0, sum2 = 0; 

    for(int i = 0; i < a.length; i++) { 
     sum1 += a[i]; 
    } 

    for(int i = 0; i < b.length; i++) { 
     sum2 += b[i]; 
    } 
} 

Pytanie 1: Czy to w czasie O (n)? Czy ma znaczenie, ile pętli (nie zagnieżdżonych) znajduje się w method1?

Pytanie 2: Co jeśli istnieje

Arrays.sort(a); 

wewnątrz method1, co to jest funkcja?

Answer 1

Pytanie 1: Czy to w O (n)?

To prawda (tutaj, n oznacza długość każdej z dwóch tablic).

Czy ma znaczenie ile pętli (nie zagnieżdżonych) jest w metodzie 1?

nie, tak długo, jak liczba pętli jest stała, a ilość powtórzeń w każdym pętli liniowa n. Bardziej formalnie, jeśli C jest trochę stała,jest O(n).

Pytanie 2: Co jeśli istnieje Arrays.sort(a);

Sortowanie jest zwykle O(n logn), a to co robi Arrays.sort(int[]) średnio. documentation jest niejasne o wydajności najgorszego scenariusza:

Algorytm ten oferuje O (n log (n)) wydajność na wielu zbiorów danych, które powodują inne quicksorts degradować do kwadratowej wydajności, i jest zwykle szybciej niż tradycyjny (one-pivot) Implementacje Quicksort.

To wyraźnie powstrzymuje się od gwarantując O(n logn) w najgorszym przypadku. Czytanie między wierszami sugeruje, że prawdopodobnie jest to O(n^2).

Warto zauważyć, że w JDK7, Arrays.sort(Object[]) używa innego algorytmu niż ten używany przez Arrays.sort(int[]). Ta pierwsza jest adaptacją TimSorta i dlatego powinna gwarantować najgorszą możliwą wydajność. Niestety, dokumentacja ponownie przestaje się nad tym wypowiadać.

Answer 2

1. a. Jest to O (n) gdzie n = długość wejścia (całkowita)
   b. Tak, liczy się liczba pętli: jeśli jest to stała liczba pętli k, to jest to O (k * n), które jest zwykle uważane za O (n), ale jeśli k> = n, to coś, co powinno być brane pod uwagę

2. Arrays.sort(a); jest zaimplementowana przy użyciu sortowania scalonego, które działa w trybie O (n log n) zarówno w sposób średni, jak i najgorszy (nie tak jak w przypadku NPE!).

Aktualizacja MrSmith42:

Z http://docs.oracle.com/javase/7/docs/api/java/util/Arrays.html:
algorytm wykorzystywany przez rodzaju (Object []) nie musi być mergesort, ale nie muszą być stabilne).

A także:

Realizacja uwaga: algorytm sortowania jest dual-P ivot Quicksort autorstwa Władimira Jarosławskiego, Jona Bentleya i Joshua Blocha. Algorytm ten oferuje wydajność O (n log (n)) w wielu zestawach danych, które powodują pogorszenie wydajności w porównaniu do wydajności kwadratowej i jest zwykle szybsza niż tradycyjne (jednozawiesienne) implementacje Quicksort.