Złożoność obliczeniowa algorytmów - okładka

Złożoność obliczeniowa algorytmów

Opublikowano Kategorie Czysty kodCzas czytania 7min

Złożoność obliczeniowa algorytmów to kluczowe zagadnienie do zrozumienia, w procesie tworzenia algorytmów. Bez jego znajomości, moim zdaniem, tworzenie efektywnych i szybkich algorytmów może być bardzo trudne, czy wręcz niemożliwe. W tym wpisie dowiesz się, czym jest złożoność obliczeniowa algorytmów, notacja dużego O, oraz poznasz najczęściej spotykane złożoności obliczeniowe.

Definicja algorytmu

Mówiąc o złożoności obliczeniowej algorytmów, warto na samym początku zdefiniować pojęcie algorytmu.

Często spotykanym opisem definiującym algorytm jest lista kroków w postaci przepisu na ciasto czy instrukcji wymiany koła w samochodzie. Takie przedstawienie algorytmu dla osoby nietechnicznej jest jak najbardziej akceptowalne. Pozwala to na zrozumienie tematu takiej osobie w stopniu dla niej akceptowalnym. Jednak takie przedstawienie definicji algorytmu w branży IT, moim zdaniem, jest niekompletne i wypada mizernie.

Algorytm to metoda, która dla zbioru danych x, należących do dopuszczalnego zbioru danych wejściowych, generuje rezultat y, należący do zbioru dopuszczalnych wyników, oraz spełnia następujące założenia:

  1. Metoda ma skończoną liczbę kroków. Niedopuszczalne jest stworzenie algorytmu nieskończonego.
  2. Każdy krok algorytmu musi być obliczalny/wykonywalny.
  3. Każdy krok algorytmu musi być zdefiniowany jednoznacznie. Przykładowo, niedopuszczalne jest zdefiniowanie kroku „wsyp cukier” – brakuje informacji: „gdzie?”, „ile?”.

Notacja dużego O

Notacja dużego O mówi nam o szybkości wykonania algorytmu. Przez szybkość mam na myśli tu ilość operacji, którą komputer musi wykonać, niekoniecznie zaś sam czas wykonania. Niemniej jednak spadek szybkości lubi iść w parze ze wzrostem czasu wykonania algorytmów.

Aby opisać algorytm za pomocą notacji dużego O, wykorzystuje się liczbę n, która wyraża liczbę elementów w zbiorze danych wejściowych przekazanych do algorytmu. Na podstawie liczby n każdy algorytm można opisać za pomocą formuły matematycznej mówiącej o liczbie operacji w kodzie, jaka musi się wykonać po podaniu zbioru wejściowego danych o rozmiarze n. Można również powiedzieć, że notacja dużego O opisuje, jak rośnie liczba operacji do wykonania przez algorytm wraz ze zwiększaniem się zbioru wejściowego.

Jednym z najprostszych przykładów złożoności obliczeniowej jest złożoność O(n). Taki poziom złożoności oznacza, że algorytm wykona tyle operacji, ile elementów będzie się znajdować w zbiorze danych wejściowych. Przykładem algorytmu o złożoności n jest poniższy prosty kod wykorzystujący pętlę for, która iteruje po zbiorze danych wejściowych.


const input: number[] = Array.from( Array( 100 ).keys() );

function multiplyBy2( input: number[] ) {
    const multipliedInput: number[] = [];

    for ( let i of input ) {
        multipliedInput.push( i*2 );
    }

    return multipliedInput;
}

console.log( multiplyBy2( input ) );

Bardzo istotnym aspektem opisywania złożoności obliczeniowej algorytmów z wykorzystaniem notacji dużego O jest fakt, że opisuje ona najmniej korzystny (najgorszy) przypadek z punktu widzenia wykonywanego algorytmu. Aby zobrazować to zagadnienie lepiej, zmodyfikowałem nieco powyższy kod.


const input1: number[] = Array.from( Array( 100 ).keys() );
const input2: number[] = Array.from( Array( 10 ).keys() );

function multiplyBy2( input: number[] ) {
    const multipliedInput: number[] = [];

    for ( let i of input ) {
        multipliedInput.push( i*2 );

         if( i*2 === 100 ) {
            return multipliedInput;
        }
    }

    return multipliedInput;
}

console.log( multiplyBy2( input1 ) );
console.log( multiplyBy2( input2 ) );

W przypadku zbioru danych input1 faktyczna liczba operacji w powyższym algorytmie nie wyniesie n, lecz n/2. Nie zmienia to jednak złożoności obliczeniowej tego algorytmu, ponieważ można znaleźć zbiór „gorszy” z punktu widzenia ilości operacji do wykonania. Zbiorem „gorszym” w tym przypadku jest na przykład input2. Oznacza to również, że przykładowo, złożoność 7n2 + 35n + 7 jest dalej złożonością n2, pomimo faktu, że dla pustego zbioru danych liczba operacji wyniesie 7.

Dlaczego złożoność obliczeniowa jest istotna?

Algorytmy opisane za pomocą notacji dużego O warto rozważać w kontekście rosnących zbiorów danych. Dwa algorytmy wykonujące tę samą czynność, lecz mającą różną złożoność mogą drastycznie różnić się wydajnością i czasem wykonania. Przykładowo, mając zbiór danych o rozmiarze n = 10000, dwa algorytmy wykonujące tę samą czynność, gdzie jeden jest opisany O(n), a drugi O(n2) różnica w liczbie obliczeń wynosi:

  • O(n) = 10000
  • O(n2) = 100000000

Gdy przy pracy z algorytmem pojawia się skala, zmniejszenie złożoności potrafi przynieść ogromny wzrost wydajności.

Często spotykane złożoności obliczeniowe

W algorytmice pewne złożoności obliczeniowe występują znacznie częściej niż inne. W dalszej części wpsiu przedstawiam najczęściej spotykane złożoności obliczeniowe:

O(1)

Jest to stała złożoność obliczeniowa. Zamiast liczby 1 można umieścić dowolną inną liczbę. Taka złożoność oznacza, że liczba operacji w takim algorytmie zawsze będzie wynosić tyle, ile wynosi stała wartość, niezależnie od rozmiaru zbioru wejściowego.

Złożoność obliczeniowa O(1)

O(n)

Tę złożoność już de facto opisałem wcześniej. Liczba operacji w algorytmie rośnie liniowo w odniesieniu do rozmiaru zbioru wejściowego.

Złożoność obliczeniowa O(n)

O(log n)

Jest to złożoność logarytmiczna. Oznacza to, że dla zbioru o rozmiarze 2n, liczba operacji wyniesie n. Tego typu złożoność często można spotkać w algorytmach wykorzystujących zasadę „dziel i rządź”, na przykład w algorytmie wyszukiwania binarnego.

Złożoność obliczeniowa O(logn)

O(n * log n)

Ten typ złożoności obliczeniowej często występuje w algorytmach sortowania, wykorzystujących zasadę „dziel i rządź”, na przykład w algorytmie sortowania przez łączenie (merge sort).

Złożoność obliczeniowa O(nlogn)

O(n2)

Tym wzorem opisana jest złożoność kwadratowa. Ten typ złożoności obliczeniowej występuje na przykład w algorytmach, które mają w sobie zagnieżdżoną pętlę for iterującą po całym zbiorze wejściowym. Stąd też, w miarę możliwości, warto rozważyć refaktoryzację kodu, jeśli w algorytmie występuje taka struktura.

Złożoność obliczeniowa O(n^2)

O(2n)

Jest to tzw. złożoność wykładnicza. W tym przypadku tak jak w przypadku stałej złożoności obliczeniowej liczbę 2 można zastąpić dowolną inną. Przykładem algorytmu wykorzystującego taką złożoność jest algorytm wykorzystywany przy ataku brutalnym (brute force attack). W przypadku hasła o długości n znaków, mającego jedynie małe litery wykorzystywane w języku angielskim oraz cyfry złożoność będzie wynosić O(36n).

Złożoność obliczeniowa O(2^n)

O(n!)

Złożoność obliczeniowa n! (n silnia) również „występuje w przyrodzie”. Przykładem algorytmu o złożoności obliczeniowej n! jest algorytm rozwiązujący problem komiwojażera.

Złożoność obliczeniowa O(n!)

Podsumowanie

Mam nadzieję, że dowiedziałeś/aś się czegoś nowego i że Twoje przyszłe algorytmy będą cechowały się jak najniższą złożonością. Serdecznie zachęcam do zapoznania się z materiałami dodatkowymi, źródłami, udostępnienia tego wpisu oraz zostawienia komentarza.

Źródła i materiały dodatkowe:

Dominik Szczepaniak

Zawodowo Senior Software Engineer w CKSource. Prywatnie bloger, fan włoskiej kuchni, miłośnik jazdy na rowerze i treningu siłowego.

Inne wpisy, które mogą Cię zainteresować

Zapisz się na mailing i odbierz e-booka

Zapisując się na mój mailing, otrzymasz darmowy egzemplarz e-booka 106 Pytań Rekrutacyjnych Junior JavaScript Developer! Będziesz też otrzymywać wartościowe treści i powiadomienia o nowych wpisach na skrzynkę e-mail.

Subscribe
Powiadom o
guest

0 komentarzy
Inline Feedbacks
View all comments