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

Pytanie

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

Co zrobiłem przed opublikowaniem pytania na SO?

Przejrzałem to , to i wiele innych linków

Ale nie, gdzie nie mogłem znaleźć jasnego i prostego wyjaśnienia, jak obliczyć złożoność czasu.

Co ja wiem ?

Powiedz kod tak prosty jak ten poniżej:

char h = 'y'; // This will be executed 1 time
int abc = 0; // This will be executed 1 time

Powiedz o pętli takiej jak ta poniżej:

for (int i = 0; i < N; i++) {        
    Console.Write('Hello World !');
}

int i = 0; Zostanie to wykonane tylko raz . Czas jest faktycznie obliczany do i=0deklaracji, a nie do niej.

i <N; Zostanie to wykonane N + 1 razy

i ++; Zostanie to wykonane N razy

Tak więc liczba operacji wymaganych przez tę pętlę wynosi

{1+ (N + 1) + N} = 2N + 2

Uwaga: To wciąż może być błędne, ponieważ nie jestem pewien, czy rozumiem, jak obliczać złożoność czasu

Co chcę wiedzieć ?

Ok, więc te małe podstawowe obliczenia, myślę, że wiem, ale w większości przypadków widziałem złożoność czasu jako

O (N), O (n2), O (log n), O (n!) .... i wiele innych ,

Czy ktoś może mi pomóc zrozumieć, w jaki sposób oblicza się złożoność czasową algorytmu? Jestem pewien, że jest wielu początkujących, takich jak ja, chcących to wiedzieć.

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

Dodaje się, ile instrukcji maszyny wykona w zależności od wielkości danych wejściowych, a następnie upraszcza wyrażenie do największego (gdy N jest bardzo duży) terminu i może zawierać dowolny stały współczynnik upraszczający.

Na przykład zobaczmy, jak uprościć 2N + 2instrukcje maszyny, aby opisać to jako sprawiedliwe O(N).

Dlaczego usuwamy dwa 2?

Interesuje nas wydajność algorytmu, gdy N staje się duże.

Rozważ dwa terminy 2N i 2.

Jaki jest względny wpływ tych dwóch terminów, gdy N staje się duży? Załóżmy, że N to milion.

Wtedy pierwszy okres to 2 miliony, a drugi to tylko 2.

Z tego powodu porzucamy wszystkie oprócz największych terminów dla dużych N.

Więc teraz przeszliśmy od 2N + 2do 2N.

Tradycyjnie jesteśmy zainteresowani wydajnością do stałych czynników .

Oznacza to, że tak naprawdę nie obchodzi nas, czy istnieje jakaś stała wielokrotność różnicy w wydajności, gdy N jest duże. Jednostka 2N i tak nie jest dobrze zdefiniowana. Możemy więc pomnożyć lub podzielić przez stały czynnik, aby uzyskać najprostsze wyrażenie.

Tak więc 2Nstaje się po prostu N.

Jest to doskonały artykuł: http://www.daniweb.com/software-development/computer-science/threads/13488/time-complexity-of-alameterm

Poniższa odpowiedź została skopiowana z góry (na wypadek, gdyby doskonały link przestał działać)

Najpopularniejszym miernikiem do obliczania złożoności czasu jest notacja Big O. To usuwa wszystkie stałe czynniki, dzięki czemu czas działania można oszacować w odniesieniu do N, gdy N zbliża się do nieskończoności. Ogólnie możesz myśleć o tym w ten sposób:

statement;

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

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

Jest liniowy. Czas działania pętli jest wprost proporcjonalny do N. Gdy N podwaja się, to także czas działania.

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

Jest kwadratowy. Czas działania dwóch pętli jest proporcjonalny do kwadratu N. Gdy N podwaja się, czas działania wzrasta 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 logarytmiczny. Czas działania algorytmu jest proporcjonalny do liczby przypadków, w których N można podzielić przez 2. Dzieje się tak, ponieważ algorytm dzieli obszar roboczy na pół przy każdej iteracji.

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

Czy N * log (N). Czas działania składa się z N pętli (iteracyjnej lub rekurencyjnej), które są logarytmiczne, dlatego algorytm jest kombinacją liniowej i logarytmicznej.

Ogólnie rzecz biorąc, robienie czegoś z każdym przedmiotem w jednym wymiarze jest liniowe, robienie czegoś z każdym przedmiotem w dwóch wymiarach jest kwadratowe, a dzielenie obszaru roboczego na pół jest logarytmiczne. Istnieją inne miary Big O, takie jak sześcienny, wykładniczy i pierwiastek kwadratowy, ale nie są one tak powszechne. Duża notacja O jest opisana jako O ( <type> )gdzie <type>jest miarą. Algorytm szybkiego sortowania zostałby opisany jako O ( N * log ( N ) ).

Zauważ, że w żadnym z tych nie wzięto pod uwagę najlepszych, średnich i najgorszych środków. Każdy miałby własną notację Big O. Zauważ też, że jest to BARDZO uproszczone wyjaśnienie. Duże O jest najbardziej powszechne, ale pokazałem też, że jest bardziej złożone. Istnieją również inne zapisy, takie jak duża omega, mała o i duża theta. Prawdopodobnie nie spotkasz ich poza kursem analizy algorytmów. ;)

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

1. Wstęp

W informatyce złożoność czasowa algorytmu określa ilościowo czas potrzebny algorytmowi na uruchomienie w funkcji długości ciągu reprezentującego dane wejściowe.

2. Duża notacja O

Złożoność czasowa algorytmu jest zwykle wyrażana za pomocą dużej notacji O, co wyklucza współczynniki i warunki niższego rzędu. Gdy wyrażone w ten sposób, złożoność czasowa jest opisywana asymptotycznie, tzn. Gdy wielkość wejściowa przechodzi w nieskończoność.

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ść czasu wynosi O (n ³ ). Więcej o tym później.

Kilka innych przykładów:

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

3. O (1) Constant Time:

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

Przykłady:

• array: dostęp do dowolnego elementu
• stos o stałym rozmiarze: metody push i pop
• kolejka o stałym rozmiarze: metody kolejkowania i usuwania kolejki

4. O (n) czas liniowy

Mówi się, że algorytm działa w czasie liniowym, jeśli jego wykonanie jest wprost proporcjonalne do wielkości wejściowej, tj. Czas rośnie liniowo wraz ze wzrostem wielkości wejściowej.

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:

• Tablica: wyszukiwanie liniowe, przemierzanie, znajdowanie minimum itp
• ArrayList: zawiera metodę
• Kolejka: zawiera metodę

5. O (log n) Czas logarytmiczny:

Mówi się, że algorytm działa w czasie logarytmicznym, jeśli jego wykonanie jest proporcjonalne do logarytmu wielkości wejściowej.

Przykład: Wyszukiwanie binarne

Przypomnijmy grę „dwadzieścia pytań” - zadaniem jest odgadnięcie wartości ukrytej liczby w przedziale. Za każdym razem, gdy zgadujesz, jesteś informowany, czy twoje domysły są zbyt wysokie, czy zbyt niskie. Gra dwudziestu pytań zakłada strategię, która wykorzystuje twoją liczbę zgadywania, aby zmniejszyć o połowę rozmiar interwału. Jest to przykład ogólnej metody rozwiązywania problemów znanej jako wyszukiwanie binarne

6. O (n ² ) Czas kwadratowy

Mówi się, że algorytm działa w czasie kwadratowym, jeśli jego wykonanie jest proporcjonalne do kwadratu wielkości wejściowej.

Przykłady:

• Sortowanie bąbelkowe
• Sortuj wybór
• Sortowanie przez wstawianie

7. Niektóre przydatne linki

• Wielkie nieporozumienia
• Określanie złożoności algorytmu
• Big O Ściągawka

Chociaż istnieją dobre odpowiedzi na to pytanie. Chciałbym podać tutaj kolejną odpowiedź z kilkoma przykładami loop.

• O (n) : Złożoność czasowa pętli jest uważana za O (n), jeżeli zmienne pętli są zwiększane / zmniejszane o stałą wartość. Na przykład następujące funkcje mają złożoność czasową O (n) .

  // 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 wykonań najbardziej wewnętrznej instrukcji. Na przykład następujące przykładowe pętle mają złożoność czasową O (n ^ 2)

  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 ma złożoność czasową O (n ^ 2) .

• O (Logn) Złożoność czasowa pętli jest uważana za O (Logn), jeżeli zmienne pętli są dzielone / mnożone przez stałą wartość.

  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 złożoność czasową O (Logn) .

• O (LogLogn) Złożoność czasową pętli uważa się za O (LogLogn), jeżeli 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.

Tak więc całkowity czas złożoności powyższego algorytmu wynosi (n + n/2 + n/3 + … + n/n), Który staje sięn * (1/1 + 1/2 + 1/3 + … + 1/n)

Ważna rzecz w seriach (1/1 + 1/2 + 1/3 + … + 1/n)jest równa O (Logn) . Zatem złożoność czasowa powyższego kodu wynosi O (nLogn) .

Ref: 1 2 3

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

1 - Podstawowe operacje (arytmetyka, porównania, dostęp do elementów tablicy, przypisanie): Czas działania 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 - W przeciwnym razie instrukcja: Biorąc maksymalny czas działania 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;

Tak więc złożoność powyższego pseudokodu wynosi T (n) = 2 + 1 + max (1, 1 + 2) = 6. Zatem jego duże oh jest wciąż stałe T (n) = O (1).

3 - Pętla (dla, podczas powtarzania): czas wykonywania tej instrukcji to liczba pętli pomnożona 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

Zatem jego złożoność wynosi T (n) = 1 + 4n + 1 = 4n + 2. Zatem T (n) = O (n).

4 - Pętla zagnieżdżona (zapętlanie w pętli wewnętrznej): Ponieważ w pętli głównej jest co najmniej jedna pętla, w czasie wykonywania tej instrukcji użyto 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 działania

Podczas analizy algorytmu występują pewne typowe czasy działania:

1. O (1) - Stały czas Stały czas oznacza, że ​​czas działania jest stały, nie ma na niego wpływu wielkość wejściowa .

2. O (n) - czas liniowy Gdy algorytm zaakceptuje n wielkość wejściową, wykona także n operacji.

3. O (log n) - Algorytm czasu logarytmicznego, który ma czas działania O (log n) jest nieco szybszy niż O (n). Zwykle algorytm dzieli problem na podprogramy o tym samym rozmiarze. 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 dzielenia i zdobywania”, które rekurencyjnie dzielą problem na podprogramy, a następnie łączą je w czasie n. Przykład: algorytm scalania sortowania.

5. O (n ² ) - Algorytm sortowania bąbelkowego w kwadratowym czasie!

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

7. O (2 ⁿ ) - Czas wykładniczy Jest bardzo wolny, ponieważ dane wejściowe stają się większe, jeśli n = 1000 000, T (n) wyniesie 21 000 000. Algorytm Brute Force ma ten czas działania.

8. O (n!) - Factorial Time NAWOLNOŚĆ !!! Przykład: problem sprzedawcy podróży (TSP)

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

Analizując kod, musisz przeanalizować go wiersz po wierszu, licząc każdą operację / rozpoznając złożoność czasu, w końcu musisz go zsumować, aby uzyskać cały 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ść sześcienną . Tutaj odgrywa rolę kolejność wzrostu.

Spójrzmy, jakie są możliwości złożoności czasowej algorytmu, można zobaczyć kolejność wzrostu, o której wspomniałem powyżej:

• Stała czasowa ma kolejność wzrostu1, na przykład:a = b + c.

• Czas logarytmiczny ma kolejność wzrostuLogN, zwykle występuje, gdy dzielisz coś na pół (wyszukiwanie binarne, drzewa, nawet pętle) lub mnożąc coś w ten sam sposób.

• Liniowy , kolejność wzrostu jestN, na przykład

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

• Liniowy porządek wzrostun*logNwystępuje zwykle w algorytmach dzielenia i podbijania.

• Sześcienny , rząd wzrostuN^3, klasyczny przykład to potrójna pętla, w której sprawdzasz 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
  

• Gwałtowny wzrost2^N, zwykle występuje, gdy przeprowadzasz wyczerpujące wyszukiwanie, na przykład sprawdzasz podzbiory jakiegoś zestawu.

Mówiąc luźniej, złożoność czasu jest sposobem podsumowania wzrostu liczby operacji lub czasu działania algorytmu wraz ze wzrostem wielkości wejściowej.

Jak większość rzeczy w życiu, przyjęcie koktajlowe może pomóc nam zrozumieć.

NA)

Po przybyciu na przyjęcie musisz uścisnąć wszystkim rękę (wykonać operację na każdym elemencie). Wraz ze wzrostem liczby uczestników Nrośnie czas / praca, aby uścisnąć dłoń każdego O(N).

Dlaczego O(N)nie cN?

Istnieje różna ilość czasu, jaki zajmuje uścisk dłoni z ludźmi. Możesz to uśrednić i uchwycić w sposób ciągły c. Ale podstawowa operacja tutaj - uścisk dłoni ze wszystkimi - zawsze byłaby proporcjonalna do O(N), bez względu na to, co cbyło. Kiedy zastanawiamy się, czy powinniśmy pójść na przyjęcie koktajlowe, często bardziej interesuje nas fakt, że będziemy musieli poznać wszystkich, niż najdrobniejsze szczegóły tego, jak wyglądają te spotkania.

O (N ^ 2)

Gospodarz koktajlu chce, abyś zagrał w głupią grę, w której wszyscy spotykają wszystkich. Dlatego musicie poznać N-1innych ludzi, a ponieważ kolejna osoba już cię spotkała, muszą poznać N-2ludzi i tak dalej. Suma tej serii to x^2/2+x/2. W miarę wzrostu liczby uczestników x^2termin staje się bardzo szybki , więc porzucamy wszystko inne.

O (N ^ 3)

Musisz spotkać się ze wszystkimi i podczas każdego spotkania musisz porozmawiać o wszystkich innych w pokoju.

O (1)

Gospodarz chce coś ogłosić. Popijają kieliszek do wina i mówią głośno. Wszyscy je słyszą. Okazuje się, że nie ma znaczenia, ilu jest uczestników, ta operacja zawsze zajmuje tyle samo czasu.

O (log N)

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

O (N log N)

Możesz znaleźć, gdzie usiąść przy stole, korzystając z powyższego algorytmu. Gdyby przy stole przyszła duża liczba osób, jedna po drugiej, i wszyscy to zrobili, zajęłoby to O (N log N) . Okazuje się, ile czasu zajmuje sortowanie dowolnej kolekcji przedmiotów, gdy trzeba je porównać.

Najlepszy / najgorszy przypadek

Przybywasz na przyjęcie i musisz znaleźć Inigo - ile to zajmie? To zależy od tego, kiedy przyjedziesz. Jeśli wszyscy się kręcą, trafiłeś w najgorszy przypadek: zajmie to trochę O(N)czasu. Jeśli jednak wszyscy siadają przy stole, zajmie to tylko trochę O(log N)czasu. A może uda Ci się wykorzystać siłę gospodarza do krzyczenia kieliszka wina i zajmie to tylko trochę O(1)czasu.

Zakładając, że host jest niedostępny, możemy powiedzieć, że algorytm znajdujący Inigo ma dolną granicę O(log N)i górną granicę O(N), w zależności od stanu drużyny po przyjeździe.

Przestrzeń kosmiczna i komunikacja

Te same pomysły można zastosować do zrozumienia, w jaki sposób algorytmy wykorzystują przestrzeń lub komunikację.

Knuth napisał miły artykuł na temat tego pierwszego zatytułowany „Złożoność pieśni” .

Twierdzenie 2: Istnieją arbitralnie długie piosenki o złożoności O (1).

DOWÓD: (dzięki Casey i Sunshine Band). Rozważmy piosenki 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 wstecz i jest tu kilka doskonałych odpowiedzi, niemniej jednak chciałem podzielić się z innymi nieco matematykami, którzy natkną się na ten post. Twierdzenie Mistrz jest inny przydatny jest, aby wiedzieć, kiedy studiuje złożoności. Nie widziałem tego w innych odpowiedziach.

O (n) to duża notacja O używana do zapisu złożoności czasowej algorytmu. Po dodaniu liczby wykonań do algorytmu otrzymamy wyrażenie takie 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ść wzrośnie lub spadnie). Teraz O (N) jest złożonością 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 wykonań dla pętli wewnętrznej wynosi n + 1, a całkowita liczba wykonań 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 dla tego algorytmu wynosi O (n ^ 2)