Big-O: si matet rritja e kodit

Dy programe, një përgjigje, shpejtësi krejt të ndryshme

Deri tani, nëse një program jepte përgjigjen e saktë, mjaftonte. Kjo ndryshon në çastin që të dhënat bëhen të mëdha. Dy programe mund të pajtohen për çdo përgjigje dhe prapë të jenë larg njëri-tjetrit: njëri mbaron menjëherë me një milion njësi, tjetri ende po punon kur ti ke ikur në shtëpi.

Pyetja që i përgjigjet ky mësim nuk është "sa sekonda i duhen?" Një laptop më i shpejtë i ndryshon sekondat, por jo sjelljen e brendshme. Pyetja e vërtetë është: ndërsa hyrja rritet, si rritet me të sasia e punës? Ajo formë e rritjes është ajo që masim, dhe Big-O është shënimi me të cilin e shkruajmë.

Numëro punën, jo orën

Të matësh një program me kronometër është i pabesueshëm. Numri varet nga makina jote, nga çfarë tjetër po ekzekuton, madje nga sa i ngrohtë është procesori. Ndaj, në vend që të masim kohën, numërojmë hapat që bën programi si funksion i madhësisë së hyrjes, të cilën e quajmë n.

Shiko këto dy cikle mbi një listë me n njësi:

# Cikli A: shiko çdo njësi një herë
for item in data:
    print(item)

# Cikli B: për çdo njësi, shiko sërish çdo njësi
for a in data:
    for b in data:
        print(a, b)

Cikli A bën n shtypje. Cikli B bën n shtypje për secilën nga n njësitë, pra n * n = n² shtypje. Në një listë me 10 kjo është 10 kundrejt 100. Në një listë me 1000 është 1000 kundrejt 1,000,000. E njëjta ide, punë tejet e ndryshme. Ndërthurja është shenja: një cikël brenda një cikli zakonisht e kthen n në n².

Big-O: forma e rritjes

Big-O e mban vetëm pjesën që ka rëndësi kur n bëhet i madh, dhe i heq konstantet e termat e vegjël. Nuk themi "rreth 3n plus 7 hapa"; themi se rritja është O(n). Tri forma mbulojnë shumicën e asaj që has një fillestar:

• O(1), konstante. Puna nuk rritet fare me n. Leximi i data[0] ose len(data) merr të njëjtën kohë, qoftë lista me dhjetë njësi apo dhjetë milionë.
• O(n), lineare. Puna rritet krah për krah me n. Një kalim mbi të dhënat, si Cikli A. Dyfisho të dhënat, dyfishohet puna.
• O(n²), kuadratike. Puna rritet me katrorin e n. Një cikël brenda një cikli, si Cikli B. Dyfisho të dhënat, katërfishohet puna.

Një shembull i punuar: a ka dublikate?

Le të themi se ke një listë numrash identifikimi të nxënësve dhe do të dish nëse ndonjë numër shfaqet dy herë. Ja përpjekja e parë e natyrshme: krahaso çdo njësi me çdo njësi që vjen pas saj.

def has_duplicate_slow(ids):
    for i in range(len(ids)):
        for j in range(i + 1, len(ids)):
            if ids[i] == ids[j]:
                return True
    return False

Funksionon, por është një cikël brenda një cikli, ndaj është O(n²). Në një klasë me 30 nxënës nuk është asgjë. Në një bazë kombëtare me një milion numra janë një trilion krahasime, dhe do të presësh shumë gjatë.

Tani përdor një vegël që e ke takuar tashmë, një set (bashkësi), që mund të kontrollojë përkatësinë thuajse menjëherë:

def has_duplicate_fast(ids):
    seen = set()
    for one in ids:
        if one in seen:
            return True
        seen.add(one)
    return False

Kjo bën një kalim të vetëm mbi listën, dhe çdo kontroll in mbi një set është afërsisht O(1), ndaj i gjithë funksioni është O(n). E njëjta përgjigje si versioni i ngadaltë, por me një milion numra mbaron sa hap e mbyll sytë. Mësimi nuk është "set-et janë magji"; është se zgjedhja e strukturës së duhur të të dhënave e ndryshoi formën e rritjes, nga n² poshtë te n.

Ai këmbim ka një kosto që ia vlen ta emërtojmë: versioni i shpejtë mban një set seen, ndaj përdor më shumë memorie për të kursyer kohë. Big-O e përshkruan edhe rritjen e memories, dhe këmbimi i kohës me hapësirën është një nga vendimet më të shpeshta që do të marrësh si programues.

Tërhiq rrëshqitësin për të parë si ndahen dy kontrolluesit e dublikateve: versioni me cikle të ndërthurura ngjitet si n², ndërsa versioni me set rritet vetëm me n.

Provo veten

1. Pse e masim rritjen e punës ndërsa n rritet, në vend që thjesht ta masim programin në sekonda te kompjuteri ynë?
2. Një funksion ka një cikël for të vetëm mbi një listë me n njësi, pa cikël brenda tij. Cila është Big-O e tij, dhe çfarë i ndodh punës kur lista dyfishohet?
3. Kontrolli i shpejtë i dublikateve është O(n) por përdor memorie shtesë për set-in seen, ndërsa i ngadalti është O(n²) por nuk përdor thuajse fare. Përshkruaj një situatë ku prapë mund të zgjidhje versionin më të ngadaltë.