Zložitosť algoritmu

street_punk · Napísal **street_punk**: 18.02.2012 21:45

Vedel by mi niekto vysvetliť, ako sa určuje konštanta c určujúca zložitosť ( napríklad bubble sortu ) f(N) = cN.N ?
Nejde mi o to výsledok, ale ako sa k nemu dopracovať.

MTK · Napísal **MTK**: 18.02.2012 22:22

Mam pocit ze "c" sa nejakym sposobom nespecifikuje to je tam koli tomu aby ked to niekto precital tak vedel ze sa tam nevykonavaju dva vnorene prazdne cykly ale ze sa v nich aj cosi robi. Konkretna hodnota c bude zavisiet od toho na akej platforme to bezi a na akej urovni to breies lebo ak s tym ides az na instrukcie tak tam budes mat povedzme c=50 pri x86 architekture ale na nejakom ARM to bude mozno 70.
V skole sme na predmete analyza a zlozitost algoritmov nikdy nevycislovali hodnotu c

street_punk · Napísal autor témy **street_punk**: 19.02.2012 8:48

Hej to viem že je časová a priestorová zložitosť a záleži od tvojho PC. Len od nás žiadajú naprogramovať bubble sort a vyčísliť tú zložitosť (naprogramované to mám, ale nechcem to sem dať nech to neni skopčené). Keď je to N.N, tak či tie N-ká nie sú prechody cyklu, ale zároveň je tam aj if, no neviem

// pridané po 6 minútach od posledného príspevku

Takto, mali sme ten algoritmus z efektívniť. Dám sem ten klasický bubble sort a na ňom, keď by mi to mohol dakto vysvetliť

Kód:

for(i = 0; i < pocet; i++)
{
   for(j = 0; j < pocet - 1; j++)
      {
         if(pole[j] > pole[j + 1])
            swap(pole[j], pole[j+1]);
      }
}

P.S.: Nepíšte mi sem prosím žiadne vylepšenia tohto algoritmu, ide mi len o tú zložitosť

dhino · Napísal **dhino**: 22.02.2012 8:59

Zlozitost algoritmu sa zvykne zjednodusene urcovat podla toho kolkokrat sa procesorovo/casovo intenzivna cast musi vykonat pre dosiahnutie vysledku. Pre funkciu, ktora je v cykle o dlzke "n" je zlozitost "O" zavisla od "n":

O(n)

Co sa tyka tvojho uveneho prikladu, ide o neoptimalizovanie bublinkove triedenie a jeho zlozitost je

O(n*n) // celkovy pocet cyklov = pocet vonkajsich * pocet vnutornych

Obcas, ak pocet cyklov zavisi od nejakych podmienok, uvadza sa minimalna a maximalna zlozitost. V tvojom pripade vsak je pocet cyklov fixne dany, takze

Omin = Omax = O(n*n)

Bublinkovy algoritmus sa da vylepsit tak, ze, pri kazdej iteracii vonkasieho cyklu skontrolujes ci bol v predchadzajucom cykle "swap" vykonany.
Ak ano, pokracujes normalne dalej. Ak nie, mozes skoncit, pretoze pole je zoradene. Pri tejto optimalizacii pre najlepsi pripad (pole je hned na ziacatku zoradene) plati:

Omin(n)

pre najhorsi pripad zlozitost zostava Omax(n*n)

Zložitosť algoritmu

Podobné témy