Új hozzászólás Aktív témák

• #2074 Lacc aktív tag axioma #2066

  Új Válasz 2019-03-11 20:10:47 #2074

  Új hozzászólás

  Összes hozzászólása itt Válaszok az összes hozzászólására itt Válaszok erre a hozzászólásra

  Privát üzenet küldése

  

  Lacc

  aktív tag

  válasz axioma #2066 üzenetére

  Röviden O(1) az csak egy kategóra, amely azt jelöli, hogy nem függ a bemeneti elemek számától, n-től.
  Megegyezés, hogy O(C) ---> O(1) kategóriának felel meg, ahol C egy konstans, ami > 0. (O(9) --> O(1) lesz)
  Másképp, O(bármely konstans) kifejezést az O(1)-nek feleltetnek meg.

  Röviden O(g(x)) = C * g(x), ahol C egy konstans, ezért mondható, hogy bármely konstans --> O(1)-nek felelthető meg, és O(g(x)) = f(x) pedig csak egy felső becslés az f(x) függvényre az adott x helyen. x --> végtelen alatt. (egyenlőség jel csalóka, tudni kell a mögöttes matekot hozzá értelemezni)

  Máshogy, O(1) azt jelöli, hogy a processzornak csak 1db műveletet kell elvégeznie, hogy teljesítsen egy feladatot. Az az, ha van n elemből álló bemeneti lista, akkor a dict-ből 1 elem kivétele csak 1 művelet, for-ral bejárni, már n művelet. Ilyenkor nem is kötelező, hogy a processzor műveletének lefutása független legyen n-től, az az f(x) függvény függhet n-től, de a rá adott felső becslésnek már O()-nak már függetlennek kell lennie.

  Dict-ből az elem kivétele még a következkő fontos kategóriát sem éri el, ami az O(log log n), ami a prioritásos sornál tűnik fel - igen van még kettő közte, de nem igazán találok arra infós példát, hogy hol számítana.

  Ha ismered a C pointerek műkődését az segít megérteni, hogy miért is O(1), egy a tömb 4-ik indexét így is eléred a C-ben a[4], ha viszont ismered a C-t, akkor tudod jól, hogy emögött valójában milyen művelet van: *(a+4), ahol annyit jelent, hogy az tömb-öt jelöli pointer-hez hozzáadik 4-et akkor megkapot a 4-ik elemet a tömbből (A tömb pointer mindig a tömb első elemére mutat!)

Új hozzászólás Aktív témák