Jak znaleźć złożoność czasową algorytmu

To jest doskonały artykuł : http://www.daniweb.com/software-development/computer-science/threads/13488/time-complexity-of-algorithm

Poniżej odpowiedź jest kopiowana z góry (w przypadku, gdy doskonały link nie działa)

Najczęstszą metryką do obliczania złożoności czasu jest notacja Big O. To usuwa wszystkie stałe czynniki tak, że czas pracy można oszacować w stosunku do N jak n zbliża nieskończoność. Ogólnie można o tym myśleć jak to:

statement;

Jest stała. Czas działania instrukcji nie zmieni się w stosunku do N.

for ( i = 0; i < N; i++ )
     statement;

Jest liniowa. Czas pracy pętli jest wprost proporcjonalny do N. gdy n podwaja się, tak samo czas pracy.

for ( i = 0; i < N; i++ ) {
  for ( j = 0; j < N; j++ )
    statement;
}

Jest kwadratowy. Czas działania obu pętli jest proporcjonalny do kwadratu N. gdy n podwaja się, czas działania zwiększa się O N * N.

while ( low <= high ) {
  mid = ( low + high ) / 2;
  if ( target < list[mid] )
    high = mid - 1;
  else if ( target > list[mid] )
    low = mid + 1;
  else break;
}

Jest logarytmiczna. Czas działania algorytmu jest proporcjonalny do liczby N można podzielić przez 2. Dzieje się tak dlatego, że algorytm dzieli obszar roboczy na pół z każdą iteracją.

void quicksort ( int list[], int left, int right )
{
  int pivot = partition ( list, left, right );
  quicksort ( list, left, pivot - 1 );
  quicksort ( list, pivot + 1, right );
}

Jest n * log ( N). Czas działania składa się z N pętli (iteracyjnych lub rekurencyjnych), które są logarytmiczne, a więc algorytm jest kombinacją liniową i logarytmiczną.

Ogólnie rzecz biorąc, robienie czegoś z każdym elementem w jednym wymiarze jest liniowe, robienie czegoś z każdym elementem w dwóch wymiarach jest kwadratowe, a dzielenie obszaru roboczego na pół jest logarytmiczne. Tam są inne Duże O miary, takie jak sześcienny, wykładniczy, i pierwiastek kwadratowy, ale nie są one prawie tak powszechne. Notacja Wielka O jest opisana jako O (), gdzie jest miarą. Algorytm quicksort byłby opisany jako O ( N * log ( N)).

Zauważ, że żadna z tych metod nie uwzględniła najlepszych, średnich i najgorszych przypadków. Każdy z nich ma swój własny zapis O. Zauważ również, że jest to bardzo uproszczone wyjaśnienie. Duże O jest najczęstsze, ale jest również bardziej złożone, że pokazałem. Tam są również inne notacje, takie jak big omega, little o i big theta. Prawdopodobnie nie spotkasz ich poza kursem analizy algorytmów. ;)

Wzięte stąd - Wprowadzenie do złożoności czasowej algorytmu

1. Wprowadzenie

W informatyce złożoność czasowa algorytmu określa ilość czasu zajmowanego przez algorytm do działania jako funkcja długości łańcucha reprezentującego dane wejściowe.

2. Notacja Big o

Złożoność czasowa algorytmu jest zwykle wyrażana za pomocą notacji big O, która wyklucza współczynniki i terminy niższego rzędu. Gdy wyrażony w ten sposób, złożoność czasowa jest opisywana asymptotycznie, tzn. gdy wielkość wejściowa idzie do nieskończoności.

Na przykład, jeśli czas wymagany przez algorytm na wszystkich wejściach o rozmiarze n wynosi co najwyżej 5n³ + 3N, asymptotyczna złożoność czasowa wynosi O (n³). Więcej na ten temat później.

Kilka przykładów:

• 1 = O (n)
• n = O (n²)
• log(n) = O (n)
• 2 n + 1 = O (n)

3. O (1) Stały Czas:

An mówi się, że algorytm działa w stałym czasie, jeśli wymaga tego samego czasu, niezależnie od wielkości wejścia.

Przykłady:

• tablica: dostęp do dowolnego elementu
• stos o stałej wielkości: metody push i pop
• Kolejka o ustalonym rozmiarze: metody enqueue i dequeue

4. O (n) czas liniowy

Mówi się, że algorytm działa w czasie liniowym, jeśli jego wykonanie w czasie jest wprost proporcjonalne do wielkości wejściowej, tzn. czas rośnie liniowo jako wielkość wejściowa podwyżki.

Rozważ następujące przykłady, poniżej Szukam liniowo elementu, który ma złożoność czasową O (n).

int find = 66;
var numbers = new int[] { 33, 435, 36, 37, 43, 45, 66, 656, 2232 };
for (int i = 0; i < numbers.Length - 1; i++)
{
    if(find == numbers[i])
    {
        return;
    }
}

Więcej Przykładów:

• Array: Linear Search, Traversing, Find minimum etc
• ArrayList: zawiera metodę
• Queue: contains method

5. O (log n) czas logarytmiczny:

Mówi się, że algorytm działa w czasie logarytmicznym, jeśli jego czas wykonania jest proporcjonalny do logarytmu wejścia rozmiar.

Przykład: Wyszukiwanie Binarne

Przypomnij grę "dwadzieścia pytań" - zadaniem jest odgadnięcie wartości ukrytej liczby w przedziale. Za każdym razem, gdy zgadujesz, dowiadujesz się, czy Twoje zgadywanie jest zbyt wysokie, czy zbyt niskie. Dwadzieścia pytań gra implikuje strategię, która wykorzystuje swój numer odgadnięcia do zmniejszenia o połowę wielkości interwału. Jest to przykład ogólnej metody rozwiązywania problemów znanej jako wyszukiwanie binarne

6. O (n2) czas kwadratowy

Algorytm mówi się, że uruchamia się w czasie kwadratowym, jeśli jego czas wykonania jest proporcjonalny do kwadratu wielkości wejściowej.

Przykłady:

• Sortuj Bańki
• Selection Sort
• Wstawianie Sortowania

7. Kilka przydatnych linków

• Big-O
• Określenie Złożoności Algorytmu
• Big O Ściągawka

Chociaż jest kilka dobrych odpowiedzi na to pytanie. Chciałbym tu podać jeszcze jedną odpowiedź z kilkoma przykładami loop.

• O (N) : złożoność czasowa pętli jest traktowana jako O (N) Jeśli zmienne pętli są zwiększane / zmniejszane o stałą ilość. Na przykład następujące funkcje mają O(N) złożoność czasową.

  // Here c is a positive integer constant   
  for (int i = 1; i <= n; i += c) {  
      // some O(1) expressions
  }
  
  for (int i = n; i > 0; i -= c) {
      // some O(1) expressions
  }
  

• O (N^C) : złożoność czasowa zagnieżdżonych pętli jest równa liczbie czas wykonania najskrytszego stwierdzenia. Na przykład następujące przykładowe pętle mają O(N^2) złożoność czasu

  for (int i = 1; i <=n; i += c) {
     for (int j = 1; j <=n; j += c) {
        // some O(1) expressions
     }
  }
  
  for (int i = n; i > 0; i += c) {
     for (int j = i+1; j <=n; j += c) {
        // some O(1) expressions
  }
  

  Na przykład sortowanie selekcji i sortowanie wstawiania mają O(N^2) złożoność czasu.

• O (Logn) złożoność czasowa pętli jest traktowana jako O(Logn) Jeśli zmienne pętli są podzielone / pomnożone przez stałą ilość.

  for (int i = 1; i <=n; i *= c) {
     // some O(1) expressions
  }
  for (int i = n; i > 0; i /= c) {
     // some O(1) expressions
  }
  

  Na przykład wyszukiwanie binarne ma o(Logn) czas złożoność.

• O (LogLogn) złożoność czasowa pętli jest traktowana jako O (LogLogn) Jeśli zmienne pętli są zmniejszane / zwiększane wykładniczo o stałą wartość.

  // Here c is a constant greater than 1   
  for (int i = 2; i <=n; i = pow(i, c)) { 
     // some O(1) expressions
  }
  //Here fun is sqrt or cuberoot or any other constant root
  for (int i = n; i > 0; i = fun(i)) { 
     // some O(1) expressions
  }
  

Jeden przykład analizy złożoności czasu

int fun(int n)
{    
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j < n; j += i)
        {
            // Some O(1) task
        }
    }    
}

Analiza :

For i = 1, the inner loop is executed n times. For i = 2, the inner loop is executed approximately n/2 times. For i = 3, the inner loop is executed approximately n/3 times. For i = 4, the inner loop is executed approximately n/4 times. ……………………………………………………. For i = n, the inner loop is executed approximately n/n times.

Zatem całkowita złożoność czasowa powyższego algorytmu wynosi (n + n/2 + n/3 + … + n/n), która staje się n * (1/1 + 1/2 + 1/3 + … + 1/n)

Najważniejszą rzeczą w serii (1/1 + 1/2 + 1/3 + … + 1/n) jest równa O (Logn) . Tak więc złożoność czasowa powyższego kodu wynosi O (nLogn).

Ref: 1 2 3

Złożoność Czasu z przykładami

1-Podstawowe operacje (arytmetyka, porównania, dostęp do elementów tablicy, przypisanie) : czas pracy jest zawsze stały O(1)

Przykład:

read(x)                               // O(1)
a = 10;                               // O(1)
a = 1.000.000.000.000.000.000         // O(1)

2 - If Then polecenie else: pobiera tylko maksymalny czas pracy z dwóch lub więcej możliwych instrukcji.

Przykład:

age = read(x)                               // (1+1) = 2
if age < 17 then begin                      // 1
      status = "Not allowed!";              // 1
end else begin
      status = "Welcome! Please come in";   // 1
      visitors = visitors + 1;              // 1+1 = 2
end;

Zatem złożoność powyższego pseudo kodu wynosi T (n) = 2 + 1 + max(1, 1+2) = 6. Stąd jego wielkie oh jest ciągle stałe T ( n) = O (1).

3 - Looping( for, while, repeat): czas wykonania polecenia jest liczbą pętli pomnożoną przez liczbę operacji wewnątrz tej pętli.

Przykład:

total = 0;                                  // 1
for i = 1 to n do begin                     // (1+1)*n = 2n
      total = total + i;                    // (1+1)*n = 2n
end;
writeln(total);                             // 1

4-zagnieżdżona pętla( looping inside looping): ponieważ w pętli głównej znajduje się co najmniej jedna pętla, czas wykonania tej instrukcji używany jest O(n^2) lub O(N^3).

Przykład:

for i = 1 to n do begin                     // (1+1)*n  = 2n
   for j = 1 to n do begin                  // (1+1)n*n = 2n^2
       x = x + 1;                           // (1+1)n*n = 2n^2
       print(x);                            // (n*n)    = n^2
   end;
end;

Wspólny Czas Pracy

Są niektóre typowe czasy pracy podczas analizy algorytmu:

1. O (1 – - Stały Czas Stały czas oznacza, że czas pracy jest stały, nie ma na niego wpływu wielkość wejściowa .

2. O (n) - czas liniowy Gdy algorytm przyjmuje n wielkości wejściowych, wykonuje również n operacji.

3. O (log n) - czas logarytmiczny Algorytm, który ma czas pracy O (log n) jest nieco szybszy niż O (n). Zwykle algorytm dzieli problem na problemy podrzędne z tym samym rozmiarem. Przykład: algorytm wyszukiwania binarnego, algorytm konwersji binarnej.

4. O (N log n) - czas liniowy Ten czas działania jest często spotykany w algorytmach "divide & conquer", które dzielą problem na pod problemy rekurencyjnie, a następnie łączą je w n czasie. Przykład: algorytm sortowania scalającego.

5. O (n²) – Czas Kwadratowy Zobacz algorytm sortowania bąbelków!

6. O (n³) – Czas sześcienny Ma tę samą zasadę z O (n²).

7. O (2ⁿ) - Czas wykładniczy Jest bardzo wolny, ponieważ wejście staje się większe, jeśli n = 1000.000, T (n) będzie 21000.000. Algorytm Brute Force ma ten czas działania.

8. O (n!)- Czas Czynnościowy NAJWOLNIEJ !!! Przykład: problem sprzedawcy podróży (TSP)

Zaczerpnięte z tego artykułu . Bardzo dobrze wyjaśnione powinno dać lekturę.

Kiedy analizujesz kod, musisz go analizować linia po linii, licząc każdą operację/rozpoznając złożoność czasu, w końcu musisz go zsumować, aby uzyskać pełny obraz.

Na przykład, możesz mieć jedną prostą pętlę o złożoności liniowej , ale później w tym samym programie możesz mieć potrójną pętlę o złożoności sześciennej , więc twój program będzie miał złożoności sześciennej. Tu wchodzi w grę kolejność funkcji wzrostu.

Let ' s zobacz, jakie są możliwości złożoności czasowej algorytmu, możesz zobaczyć kolejność wzrostu, o której wspomniałem powyżej:

• stały CZAS ma kolejność wzrostu 1, na przykład: a = b + c.

• Czas logarytmiczny ma kolejność wzrostu LogN, zwykle występuje kiedy dzielisz coś na pół (wyszukiwanie binarne, drzewa, nawet pętle) lub mnożąc coś w tym samym sposób.

• / align = " left, kolejność wzrostu to N, na przykład

  int p = 0;
  for (int i = 1; i < N; i++)
    p = p + 2;
  

• Linearithmic, kolejność wzrostu to n*logN, zwykle występuje w algorytmach divide and conquer.

• Cubic, kolejność wzrostu N^3, klasycznym przykładem jest potrójna pętla, w której sprawdzamy wszystkie trojaczki:

  int x = 0;
  for (int i = 0; i < N; i++)
     for (int j = 0; j < N; j++)
        for (int k = 0; k < N; k++)
            x = x + 2
  

• wykładnicza, kolejność wzrostu 2^N, zwykle występuje, gdy wykonujesz wyczerpujące wyszukiwanie, na przykład sprawdzasz podzbiory jakiegoś zestawu.

Luźno mówiąc, złożoność czasowa jest sposobem podsumowania, w jaki sposób liczba operacji lub czas wykonania algorytmu rośnie wraz ze wzrostem rozmiaru danych wejściowych.

O (N)

Kiedy przyjedziesz na imprezę, musisz uścisnąć wszystkim rękę (wykonać operację na każdym przedmiocie). Wraz ze wzrostem liczby uczestników N, Czas / Praca, której potrzebujesz, aby uścisnąć wszystkim dłoń, wzrasta wraz z O(N).

Dlaczego O(N) a nie cN?

Jest różnica w ilości czasu potrzebnego do uściśnięcia dłoni ludziom. Możesz to uśrednić i uchwycić w stałej c. Ale podstawowa operacja tutaj - - - uściskanie dłoni wszystkim - - - zawsze byłaby proporcjonalna do O(N), bez względu na to, co c było. Zastanawiając się, czy powinniśmy iść na przyjęcie koktajlowe, często bardziej interesuje nas fakt, że będziemy musieli spotkać się ze wszystkimi, niż w chwili szczegóły jak wyglądają te spotkania.

O (N^2)

O (N^3)

Musisz spotkać się z innymi i podczas każdego spotkania musisz mówić o wszystkich innych w pokoju.

O(1)

O (log N)

Gospodarz położył wszystkich na tabela w kolejności alfabetycznej. Gdzie jest Dan? Musisz wiedzieć, że musi być gdzieś pomiędzy Adamem i Mandy (na pewno nie między Mandy i Zachem!). Biorąc to pod uwagę, czy jest między George ' em a Mandy? Nie. Musi być między Adamem i Fredem, i między Cindy i Fredem. I tak dalej... możemy skutecznie zlokalizować dana, patrząc na połowę zestawu, a następnie połowę tego zestawu. Ostatecznie przyjrzymy się o(log_2 N) jednostkom.

O (N log N)

Można znaleźć, gdzie usiąść na tabela wykorzystująca powyższy algorytm. Jeśli duża liczba ludzi przychodziła do stołu, jeden po drugim, i wszyscy to robili, zajęłoby to O(N log N) czas. Okazuje się, jak długo trwa sortowanie dowolnej kolekcji przedmiotów, gdy trzeba je porównać.

Najlepszy / Najgorszy Przypadek

Przyjeżdżasz na imprezę i musisz znaleźć Inigo - jak długo to potrwa ? To zależy od tego, kiedy przyjedziesz. Jeśli wszyscy kręcą się wokół ciebie, trafiłeś w najgorszy przypadek: zajmie to O(N) Czas. Jeśli jednak wszyscy siedzą przy stole, zajmie to tylko O(log N) Czas. A może możesz wykorzystać siłę okrzyku Wineglass gospodarza i zajmie to tylko O(1) czas.

Zakładając, że host jest niedostępny, możemy powiedzieć, że algorytm Inigo-finding ma dolną granicę O(log N) i górną granicę O(N), w zależności od stanu strony po przybyciu.

Przestrzeń I Komunikacja

Te same idee można zastosować do zrozumienia, jak algorytmy wykorzystują przestrzeń lub komunikację.

Knuth napisał ładną pracę o tym pierwszym zatytułowaną "złożoność piosenek" .

Twierdzenie 2: istnieją dowolnie długie utwory o złożoności o (1).

Dowód: (z powodu Casey i zespołu Sunshine). Rozważmy utwory Sk zdefiniowane przez (15), ale z

V_k = 'That's the way,' U 'I like it, ' U
U   = 'uh huh,' 'uh huh'

Dla wszystkich k.

Wiem, że to pytanie sięga daleko wstecz i istnieje kilka doskonałych odpowiedzi tutaj, jednak chciałem podzielić się innym bitem dla matematycznie myślących ludzi, którzy będą natknąć się w tym poście. Twierdzenie mistrza jest kolejną użyteczną rzeczą, którą należy wiedzieć podczas badania złożoności. Nie widziałem tego w innych odpowiedziach.

O (N) jest dużym zapisem O używanym do zapisu złożoności czasowej algorytmu. Po zsumowaniu liczby egzekucji w algorytmie otrzymasz wyrażenie w wyniku jak 2N+2, w tym wyrażeniu N jest terminem dominującym (termin mający największy wpływ na wyrażenie, Jeśli jego wartość wzrasta lub zmniejsza się). Teraz O (N) jest komleksją czasu, podczas gdy N jest terminem dominującym. Przykład

For i= 1 to n;
  j= 0;
while(j<=n);
  j=j+1;

Tutaj całkowita liczba egzekucji dla pętli wewnętrznej wynosi n+1, a całkowita liczba egzekucji dla pętli zewnętrznej wynosi n (n+1) / 2, więc całkowita liczba wykonań dla całego algorytmu wynosi n+1 + n (n+1/2) = (N^2+3n)/2. tutaj N^2 jest terminem dominującym, więc złożoność czasowa tego algorytmu wynosi O (N^2)