Az idő összetettsége A-tól Z-ig (I. rész)

Minden, amit tudnod kell

Bevezetés

Az időbonyolultság megértésének fontossága az algoritmus tervezésében:

Az időbonyolultság kritikus fogalom az algoritmus tervezésében, mivel egy algoritmus hatékonyságát és teljesítményét méri.

Az idő összetettségének mélyreható megértése lehetővé teszi számunkra, hogy megjósoljuk, hogyan skálázódik az algoritmus végrehajtási ideje a bemeneti méret növekedésével, lehetővé téve számunkra a leghatékonyabb megoldás kiválasztását.

Áttekintés arról, hogy a cikk az idő összetettségének és jelentőségének magyarázatára összpontosít:

Az időbonyolultság fogalma, bevezetve a széles körben használt Big O jelölést az időbonyolultság kifejezésére.

Gyakorlati példákon keresztül különféle időbonyolítási osztályokat tárunk fel, és elemezzük azok következményeit.

Ezenkívül megvitatjuk az időbonyolultság elemzésének technikáit, a gyakori elkerülendő buktatókat, valamint a hatékony időbonyolultságú algoritmusok kiválasztásának valós fontosságát.

Az idő összetettségének megértése

Az időbonyolultság meghatározása és kapcsolata az algoritmus hatékonyságával:

Az időbonyolultság arra utal, hogy mennyi időre van szüksége egy algoritmusnak a végrehajtásához, a bemeneti méret függvényében.

Ez egy alapvető fogalom az algoritmuselemzésben, és segít megérteni, hogyan skálázódik egy algoritmus végrehajtási ideje nagyobb bemenetekkel.

Az időbonyolultság szorosan összefügg az algoritmus hatékonyságával, mivel egy algoritmus hatékonyságát időben számszerűsíti.

A Big O jelölés, mint az időbonyolultság kifejezésére szolgáló szabványos jelölés magyarázata:

A Big O jelölés egy széles körben használt jelölés az idő összetettségének kifejezésére.

A bemeneti méret növekedésével egy algoritmus végrehajtási idejének növekedési sebességének felső korlátját biztosítja.

A Big O jelölésnél figyelmen kívül hagyjuk az állandó tényezőket és az alacsonyabb rendű kifejezéseket, és kizárólag a növekedési ütemet meghatározó domináns kifejezésre összpontosítunk.

Intuíció az időkomplexitás elemzése mögött:

Az időbonyolultság elemzése során meg kell érteni, hogyan növekszik egy algoritmus végrehajtási ideje a bemeneti méret növekedésével.

Arra összpontosít, hogy számszerűsítse az algoritmus teljesítményének változását a bemenethez képest.

Az algoritmus szerkezetének, ciklusainak és rekurzív hívásainak vizsgálatával azonosíthatjuk az algoritmus azon részeit, amelyek a leginkább hozzájárulnak az algoritmus időbeli összetettségéhez.

Common Time Complexity osztályok

O(1) – Állandó idejű összetettség

Az állandó időbonyolítású algoritmusok végrehajtási ideje fix, függetlenül a bemenet méretétől.

Ezek az algoritmusok állandó számú műveletet hajtanak végre, így rendkívül hatékonyak.

Az állandó időbonyolultságot mutató kód:

#include <iostream>

using namespace std;

void printFirstElement(int arr[], int size) {
    if (size > 0) {
        cout << "First element: " << arr[0] << endl;
    }
}

int main() {
    int array[] = {1, 2, 3, 4, 5};
    int size = 5;
    printFirstElement(array, size);

    return 0;
}

Ebben a kódban a printFirstElement() függvény egy tömb első elemét nyomtatja ki.

A tömb méretétől függetlenül a függvény állandó számú műveletet hajt végre, mivel csak az első elemhez fér hozzá.

Így ennek a műveletnek az időbonyolultsága O(1).

O(log n) – Logaritmikus időbonyolultság

A logaritmikus időbonyolítású algoritmusok végrehajtási ideje logaritmikusan növekszik a bemeneti mérettel.

Ezek az algoritmusok minden lépésben hatékonyan osztják fel a beviteli területet, és exponenciálisan csökkentik a probléma méretét.

A logaritmikus időbonyolultságot mutató kód:

#include <iostream>

using namespace std;

int binarySearch(int arr[], int size, int target) {
    int left = 0;
    int right = size - 1;

    while (left <= right) {
        int mid = left + (right - left) / 2;

        if (arr[mid] == target) {
            return mid;
        }
        else if (arr[mid] < target) {
            left = mid + 1;
        }
        else {
            right = mid - 1;
        }
    }

    return -1;
}

int main() {
    int array[] = {1, 2, 3, 4, 5};
    int size = 5;
    int target = 3;

    int result = binarySearch(array, size, target);

    if (result != -1) {
        cout << "Element found at index " << result << endl;
    }
    else {
        cout << "Element not found" << endl;
    }

    return 0;
}

A kódrészlet egy bináris keresési algoritmust mutat be, amely hatékonyan keres egy célértéket egy rendezett tömbben.

Minden iterációban az algoritmus kettéosztja a keresési teret, ami logaritmikus időbonyolultságot eredményez. Ahogy a bemenet mérete megduplázódik, a szükséges iterációk száma csak eggyel nő.

O(n) – Lineáris időbonyolultság

A lineáris időbonyolultságú algoritmusok végrehajtási ideje lineárisan növekszik a bemeneti mérettel.

Ezek az algoritmusok általában azt jelentik, hogy a bemenet minden elemét egyszer meglátogatják.

A lineáris időbonyolultságot bemutató kódrészlet:

#include <iostream>

using namespace std;

void printElements(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;
}

int main() {
    int array[] = {1, 2, 3, 4, 5};
    int size = 5;
    printElements(array, size);

    return 0;
}

Itt a függvény iterál a tömbön, és minden elemet egyszer meglátogat, ami O(n) lineáris időbonyolultságot eredményez.

A végrehajtási idő lineárisan növekszik a tömb méretével.

O(n log n) – Linearitmikus időbonyolultság

A linearitmikus időbonyolultságú algoritmusok végrehajtási ideje lineárisan növekszik, megszorozva a bemeneti méret logaritmusával.

Számos hatékony rendezési algoritmus, mint például az egyesített rendezés és a kupacrendezés, ebbe a kategóriába tartozik.

A linearitmikus időbonyolultságot bemutató kód:

#include <iostream>
#include <algorithm>

using namespace std;

void sortArray(int arr[], int size) {
    sort(arr, arr + size);
}

int main() {
    int array[] = {5, 2, 4, 1, 3};
    int size = 5;
    sortArray(array, size);

    for (int i = 0; i < size; i++) {
        cout << array[i] << " ";
    }
    cout << endl;

    return 0;
}

sort() függvényt a C++ szabványos könyvtárából. A hatékony rendezési algoritmusok, mint például a belsőleg rendezés alapján használt algoritmusok, általában O(n log n) időbonyolítással rendelkeznek.

A végrehajtási idő lineárisan növekszik a bemeneti mérettel, de a logaritmikus tényező csökkenti a szükséges műveletek számát.

O(n²) – Kvadratikus időbonyolultság

A kvadratikus időbonyolítású algoritmusok végrehajtási ideje négyzetesen nő a bemeneti mérettel.

Ezek az algoritmusok beágyazott hurkokkal rendelkeznek, ami jelentősen megnöveli a műveletek számát a nagyobb bemeneteknél.

A kvadratikus időbonyolultságot bemutató kód:

#include <iostream>

using namespace std;

void printPairs(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size; j++) {
            cout << arr[i] << "-" << arr[j] << " ";
        }
        cout << endl;
    }
}

int main() {
    int array[] = {1, 2, 3};
    int size = 3;
    printPairs(array, size);

    return 0;
}

Beágyazott hurkokat használ, ami O(n²) kvadratikus időbonyolítást eredményez.

Ahogy a tömb mérete megduplázódik, a szükséges iterációk száma négyszeresére nő.

O(2^n) – Exponenciális időbonyolultság

Az exponenciális időbonyolítású algoritmusok végrehajtási ideje exponenciálisan növekszik a bemeneti mérettel.

Ezek az algoritmusok általában magukban foglalják az összes lehetséges részhalmaz vagy kombináció feltárását, ami a műveletek gyors növekedéséhez vezet.

Az exponenciális időbonyolultságot bemutató kód:

#include <iostream>

using namespace std;

int powerOfTwo(int n) {
    if (n == 0) {
        return 1;
    }
    else {
        return 2 * powerOfTwo(n - 1);
    }
}

int main() {
    int n = 5;
    int result = powerOfTwo(n);

    cout << "2 raised to the power of " << n << " is: " << result << endl;

    return 0;
}

A kódrészlet egy rekurzív függvényt mutat be a 2 kiszámításához egy adott szám hatványára emelve.

A függvény azO(2^n) exponenciális időbonyolultságát követi, mivel minden rekurzív hívás két további hívásra ágazik.

A bemeneti méret növekedésével a rekurzív hívások és a szükséges műveletek száma exponenciálisan nő.

Az idő összetettségének elemzése

Az időbonyolultság elemzésének technikái, beleértve a műveletek számlálását, valamint a hurkok és rekurzív hívások figyelembevételét:

Egy algoritmus időbeli összetettségének elemzésekor a műveletek számlálása, valamint a hurkok és rekurzív hívások figyelembevétele kulcsfontosságú technikák:

Műveletek számlálása: Az egyik megközelítés az, hogy az algoritmus által végrehajtott műveletek számát a bemeneti méret függvényében számolják meg.

Ez aritmetikai műveletekből, összehasonlításokból vagy függvényhívásokból áll, valamint annak meghatározásából, hogy ezek hogyan járulnak hozzá az általános időbonyolultsághoz.

Curkok elemzése: Az iterációk számának és a ciklusokon belül végrehajtott műveleteknek a vizsgálatával felmérhetjük azok hozzájárulását a teljes időbonyolultsághoz.

Ebbe beletartozik a beágyazott hurkok azonosítása, valamint annak mérlegelése, hogy a hurokváltozók hogyan változnak a bemeneti mérettel.

Az időbonyolultság elemzése:

#include <iostream>

using namespace std;

void printNumbers(int n) {
    for (int i = 0; i < n; i++) {
        cout << i << " ";
    }
}

int main() {
    int n = 10;
    printNumbers(n);

    return 0;
}

Ebben a kódban a printNumbers() függvény a0-tól n-1-ig terjedő számokat ír ki hurok segítségével.

A ciklus megfigyelésével megállapíthatjuk, hogy a ciklus n-szer iterál, ami lineáris kapcsolatot eredményez a bemeneti mérettel.

Ezért ennek a műveletnek az időbonyolultságaO(n).

Domináns kifejezések azonosítása és az időbonyolultság kifejezéseinek egyszerűsítése:

Az időbonyolultsági kifejezések gyakran több kifejezést tartalmaznak, amelyek egy algoritmuson belül különböző műveleteket vagy ciklusokat képviselnek.

Az általános időbonyolultság meghatározásához fontos azonosítani a domináns kifejezést – azt a kifejezést, amely a leggyorsabban növekszik a bemeneti méret növekedésével.

Az alacsonyabb rendű kifejezések és az állandó tényezők figyelmen kívül hagyása lehetővé teszi, hogy a legjelentősebb tényezőre összpontosítsunk, amely meghatározza az algoritmus végrehajtási idejének növekedési ütemét.

Az időbonyolultság kifejezését egyszerűsítő kód:

#include <iostream>

using namespace std;

void printPairs(int n) {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << i << "-" << j << " ";
        }
    }
}

int main() {
    int n = 5;
    printPairs(n);

    return 0;
}

Ebben a kódban aprintPairs() függvény kinyomtatja az összes lehetséges számpárt 0-tól n-1-ig beágyazott hurkok használatával.

A kód elemzésével megfigyelhetjük, hogy mindkét ciklusn-szer iterál.

Ennek eredményeként az iterációk teljes száman * n = n^2.

Így ennek a műveletnek az időbonyolultságaO(n^2).

Legjobb, legrosszabb és átlagos eset-időbeli összetettségi elemzés:

Az időbeli összetettség elemzése különböző forgatókönyveket vehet figyelembe, beleértve a legjobb, a legrosszabb és az átlagos eseteket is.

A legjobb eset elemzése: Ez az elemzés meghatározza azt a minimális végrehajtási időt, amelyet egy algoritmus elérhet egy adott bemenet esetén.

Ez a legkedvezőbb forgatókönyvet képviseli, ahol az algoritmus kiemelkedően jól teljesít.
A legjobb eset időbeli összetettségét Ω(g(n)) jelöli.

A legrosszabb eset elemzése: Ez az elemzés arra a maximális végrehajtási időre összpontosít, amelyet egy algoritmus tapasztalhat egy adott bemenet esetén.

Azt aforgatókönyvet ábrázolja, ahol az algoritmus a leggyengébb teljesítményt nyújtja. A legrosszabb eset időbonyolultságát O(g(n))-ként jelöljük.

Átlagos esetelemzés: Ez az elemzés figyelembe veszi a különböző bemenetek várható végrehajtási idejét, feltételezve a bemenetek valószínűségi eloszlását.

Betekintést nyújtaz algoritmus átlagos teljesítményébe.
Az esetek átlagos időbeli összetettségét Θ(g(n)) jelöljük.

Különböző esetelemzéseket bemutató kód:

#include <iostream>

using namespace std;

int findElement(int arr[], int size, int target) {
    for (int i = 0; i < size; i++) {
        if (arr[i] == target) {
            return i;
        }
    }
    return -1;
}

int main() {
    int array[] = {1, 2, 3, 4, 5};
    int size = 5;
    int target = 3;

    int result = findElement(array, size, target);

    if (result != -1) {
        cout << "Element found at index " << result << endl;
    }
    else {
        cout << "Element not found" << endl;
    }

    return 0;
}

A kód egy olyan függvényt mutat be, amely egy tömbben célelemet keres.

A legjobb eset esetén, ahol a cél az első indexnél található, az időbeli összetettség O(1).

A legrosszabb forgatókönyv esetén, ahol a cél nincs jelen, vagy nem található az utolsó indexnél, az időbonyolultság O(n).

Az átlagos eset időbeli összetettsége szintén O(n), ha a célok egyenletes eloszlását feltételezzük.

A Medium Partner Program jelenleg inaktív az országom határain belül. Ha szeretné felajánlani a támogatását:

https://www.buymeacoffee.com/SannanA

Level Up kódolás

Köszönjük, hogy közösségünk tagja vagy! Mielőtt mész:

• 👏 Tapsolj a történetért és kövesd a szerzőt 👉
• 📰 Tekintse meg a Level Up Coding kiadvány további tartalmát
• 💰 Ingyenes kódolási interjú tanfolyam ⇒ Tanfolyam megtekintése
• 🧠 AI eszközök ⇒ Megtekintés most

🔔 Kövess minket: Twitter | LinkedIn | "Hírlevél"

🚀👉 Csatlakozzon a Level Up tehetséggondozó csapathoz, és találjon egy csodálatos munkát