Ogólnie rzecz biorąc, decydowanie o złożoności algorytmu jest teoretycznie niemożliwe.

for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        System.out.println("*");
    }
}

Teraz chcemy przeanalizować jego złożoność, więc dodajmy prosty licznik, który zlicza liczbę egzekucji wewnętrznej linii:

int counter = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        System.out.println("*");
        counter++;
    }
}

Ponieważ System.Wynocha.linia println nie ma znaczenia, usuńmy ją:

int counter = 0;
for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
        counter++;
    }
}

Teraz, gdy my jeśli zostanie tylko licznik, możemy oczywiście uprościć wewnętrzną pętlę out:

int counter = 0;
for (int i = 0; i < n; i++) {
    counter += n;
}

... ponieważ wiemy, że przyrost jest uruchamiany dokładnie n razy. I teraz widzimy, że licznik jest zwiększany o N dokładnie n razy, więc upraszczamy to do:

int counter = 0;
counter += n * n;

I pojawiliśmy się z (poprawnym) O(n²) złożoność:) jest w kodzie:)

Spójrzmy jak to działa dla rekurencyjnego kalkulatora Fibonacciego:

int fib(int n) {
  if (n < 2) return 1;
  return fib(n - 1) + fib(n - 2);
}

Zmień procedura tak, że zwraca liczbę iteracji spędzonych w niej zamiast rzeczywistych liczb Fibonacciego:

int fib_count(int n) {
  if (n < 2) return 1;
  return fib_count(n - 1) + fib_count(n - 2);
}

To wciąż Fibonacci! :) Wiemy więc teraz, że rekurencyjny Kalkulator Fibonacciego ma złożoność O(F (n)), gdzie F jest samą liczbą Fibonacciego.

Ok, spójrzmy na coś ciekawszego, powiedzmy proste (i nieefektywne) połączenia:

void mergesort(Array a, int from, int to) {
  if (from >= to - 1) return;
  int m = (from + to) / 2;
  /* Recursively sort halves */
  mergesort(a, from, m);
  mergesort(m, m,    to);
  /* Then merge */
  Array b = new Array(to - from);
  int i = from;
  int j = m;
  int ptr = 0;
  while (i < m || j < to) {
    if (i == m || a[j] < a[i]) {
      b[ptr] = a[j++];
    } else {
      b[ptr] = a[i++];
    }
    ptr++;
  }
  for (i = from; i < to; i++)
    a[i] = b[i - from];
}

Ponieważ nie interesuje nas rzeczywisty wynik, ale złożoność, zmieniamy rutynę tak, aby w rzeczywistości zwraca liczbę jednostek wykonanych prac:

int mergesort(Array a, int from, int to) {
  if (from >= to - 1) return 1;
  int m = (from + to) / 2;
  /* Recursively sort halves */
  int count = 0;
  count += mergesort(a, from, m);
  count += mergesort(m, m,    to);
  /* Then merge */
  Array b = new Array(to - from);
  int i = from;
  int j = m;
  int ptr = 0;
  while (i < m || j < to) {
    if (i == m || a[j] < a[i]) {
      b[ptr] = a[j++];
    } else {
      b[ptr] = a[i++];
    }
    ptr++;
    count++;
  }
  for (i = from; i < to; i++) {
    count++;
    a[i] = b[i - from];
  }
  return count;
}

Następnie usuwamy te linie, które faktycznie nie wpływają na liczenie i upraszczamy:

int mergesort(Array a, int from, int to) {
  if (from >= to - 1) return 1;
  int m = (from + to) / 2;
  /* Recursively sort halves */
  int count = 0;
  count += mergesort(a, from, m);
  count += mergesort(m, m,    to);
  /* Then merge */
  count += to - from;
  /* Copy the array */
  count += to - from;
  return count;
}

Jeszcze trochę upraszczam:

int mergesort(Array a, int from, int to) {
  if (from >= to - 1) return 1;
  int m = (from + to) / 2;
  int count = 0;
  count += mergesort(a, from, m);
  count += mergesort(m, m,    to);
  count += (to - from) * 2;
  return count;
}

Możemy teraz zrezygnować z tablicy:

int mergesort(int from, int to) {
  if (from >= to - 1) return 1;
  int m = (from + to) / 2;
  int count = 0;
  count += mergesort(from, m);
  count += mergesort(m,    to);
  count += (to - from) * 2;
  return count;
}

Teraz widzimy, że w rzeczywistości wartości bezwzględne from I to nie mają już znaczenia, ale tylko ich odległość, więc modyfikujemy to do: {18]}

int mergesort(int d) {
  if (d <= 1) return 1;
  int count = 0;
  count += mergesort(d / 2);
  count += mergesort(d / 2);
  count += d * 2;
  return count;
}

A potem dochodzimy do:

int mergesort(int d) {
  if (d <= 1) return 1;
  return 2 * mergesort(d / 2) + d * 2;
}

Tutaj oczywiście d na pierwszym wywołaniu jest rozmiar tablicy do posortowania, więc masz powtarzalność dla złożoności M (x) (to jest na widoku w drugiej linii:)

M(x) = 2(M(x/2) + x)

I to trzeba rozwiązać, aby dostać się do rozwiązania formularza zamkniętego. Najłatwiej to zrobić zgadując rozwiązanie M (x) = X log x i sprawdzając po prawej stronie:

2 (x/2 log x/2 + x)
        = x log x/2 + 2x
        = x (log x - log 2 + 2)
        = x (log x - C)

I sprawdzić, czy jest asymptotycznie równoważna lewej stronie:

x log x - Cx
------------ = 1 - [Cx / (x log x)] = 1 - [C / log x] --> 1 - 0 = 1.
x log x

Mimo, że jest to zbyt uogólnienie, lubię myśleć o Big-O w kategoriach list, gdzie długość listy wynosi N pozycji.

Tak więc, jeśli masz pętlę for, która iteruje nad wszystkim na liście, jest to O (N). W kodzie masz jedną linijkę, która (w izolacji sama w sobie) wynosi 0 (N).

for (int i = 0; i < n; i++) {

Jeśli masz pętlę for zagnieżdżoną w innej pętli for i wykonujesz operację na każdym elemencie na liście, która wymaga spojrzenia na każdy element na liście, to jesteś wykonywanie operacji N razy dla każdego z N elementów, a więc O (N^2). W powyższym przykładzie masz w rzeczywistości zagnieżdżoną inną pętlę for wewnątrz pętli for. Można więc myśleć o tym tak, jakby każda pętla for miała wartość 0(N), A następnie, ponieważ są zagnieżdżone, pomnożyć je razem dla całkowitej wartości 0(N^2).

Odwrotnie, jeśli robisz tylko szybką operację na pojedynczym elemencie, to będzie to O(1). Nie ma "listy długości n" do przejrzenia, tylko jeden raz operation.To umieścić to w kontekście, w twój przykład powyżej, operacja:

if (i % 2 ==0)

Jest 0(1). Ważne nie jest "Jeśli", ale fakt, że sprawdzenie, czy pojedynczy element jest równy innemu elementowi, jest szybką operacją na pojedynczym elemencie. Podobnie jak poprzednio, Instrukcja if jest zagnieżdżona wewnątrz zewnętrznej pętli for. Jednakże, ponieważ jest to 0 (1), wtedy mnożymy wszystko przez '1', a więc nie ma 'zauważalnego' wpływu w ostatecznym obliczeniu czasu działania całej funkcji.

Do logów, oraz do czynienia z bardziej złożone sytuacje (jak ta sprawa liczenia do j lub i, a nie tylko znowu n), chciałbym wskazać Ci bardziej eleganckie Wyjaśnienie tutaj.

Lubię używać dwóch rzeczy do notacji Big-O: standardowego Big-O, co jest najgorszym scenariuszem, i średniego Big-O, co zwykle się dzieje. Pomaga mi to również pamiętać, że notacja Big-O stara się przybliżać czas pracy jako funkcję N, liczbę wejść.

TA wyjaśnił to czymś w rodzaju kombinacji. Jak to jest N Wybierz 2 = (n (n-1))/2 = N^2 + 0,5, następnie usuń stałą, aby stała stała się n^2. Mogę umieścić wartości testowe int i spróbować, ale jak czy ta kombinacja wchodzi w grę?

Jak już mówiłem, normalny big-O to najgorszy scenariusz. Możesz spróbować policzyć ile razy każda linia jest wykonywana, ale prostsze jest po prostu spojrzeć na pierwszy przykład i powiedzieć, że istnieją dwie pętle na długości n, jedna osadzona w drugiej, więc jest to n * N. gdyby były one jedna po drugiej, to byłoby n + n, równe 2N. ponieważ jest to przybliżenie, po prostu mówisz n lub liniowe.

Co jeśli jest deklaracja if? Jak jest złożoność ustalona?

To jest miejsce, gdzie dla mnie średnia sprawa i najlepszy przypadek bardzo pomaga uporządkować moje myśli. W najgorszym przypadku ignorujesz if I mówisz n^2. W przeciętnym przypadku, na przykład, masz pętlę nad n, z inną pętlą nad częścią n, która dzieje się w połowie czasu. Daje to n * n/x / 2 (x jest tym, co ułamek n zostaje zapętlony w osadzonych pętlach. To daje n^2 / (2x), więc dostaniesz n^2 tak samo. To dlatego, że jego / align = "left" /

Wiem, że to nie jest kompletna odpowiedź na twoje pytanie, ale mam nadzieję, że rzuci jakieś światło na przybliżanie złożoności kodu.

Jak zostało powiedziane w odpowiedziach powyżej moich, nie jest wyraźnie możliwe określenie tego dla wszystkich fragmentów kodu; chciałem tylko dodać pomysł użycia średniej wielkości liter Big-O do dyskusji.

Dla pierwszego fragmentu, to tylko n^2, ponieważ wykonujesz n operacji n razy. Jeśli {[1] } została zainicjowana na i, lub poszła do i, Wyjaśnienie, które zamieściłeś byłoby bardziej odpowiednie, ale w obecnym stanie nie jest.

Dla drugiego fragmentu, można łatwo zobaczyć, że w połowie czasu pierwszy będzie wykonywany, a drugi będzie wykonywany w drugiej połowie czasu. W zależności od tego, co tam jest (miejmy nadzieję, że zależy to od n), możesz przepisać równanie jako rekurencyjny.

Równania rekurencyjne (w tym trzeci fragment) można zapisać jako takie: trzeci pojawi się jako

T(n) = T(n-1) + 1

Które możemy łatwo zobaczyć to O (n).

Big-O jest tylko przybliżeniem, nie mówi, jak długo algorytm zajmuje wykonanie, mówi tylko coś o tym, jak długo trwa, gdy rozmiar jego wejścia rośnie.

Więc jeśli wejście jest wielkości N i algorytm obliczy wyrażenie stałej złożoności: O (1) N razy, złożoność algorytmu jest liniowa: O (N). Jeśli wyrażenie ma złożoność liniową, algorytm ma złożoność kwadratową: O (N*N).

Niektóre wyrażenia mają złożoność wykładniczą: O(N^N) lub złożoność logarytmiczna: o (log N). Dla algorytmu z pętlami i rekurencją, mnożenie złożoności każdego poziomu pętli i / lub rekurencji. Pod względem złożoności pętla i rekurencja są równoważne. Algorytm, który ma różne złożoności na różnych etapach algorytmu, wybierz najwyższą złożoność i Ignoruj resztę. I wreszcie, wszystkie złożoności stałe są uważane za równoważne: O(5) jest taka sama jak O(1), O (5*N) jest taka sama jak O (N).