[ronek22]

Mam taki prosty algorytm równoległy i ma on prace W(n) = O(n)
No i to jest zrozumiałe, bo ta pierwsze pętla to determinuje.
Mam problem z określeniem jaką pracę ma technika drzewa zbalansowanego, czyli fragment od 3 do 5 linii.
Jedna petla jest O(log n) i ta w srodku imo licze jako O(n) czy moze powinienem jako O(1)?

#algorytmy #programowanie #algorytmyrownolegle

[Defined]

@ronek22: Wydaje mi się, że pętla 4 wykonuje O(n) operacji, którą wykonujesz log(n) razy

[ronek22]

@Defined: Tez mi się tak wydaje, i nie kumam dlaczego mam podane, ze praca jest O(n), a nie O(n*log n)

[3denos]

@ronek22: logarytm jest funkcja odwrotna do potegowania, a zlozenie funkcji odwrotnych daje id x, funkcje identycznosciowa. Stad n/n = 1 operacji.

[ronek22]

@3denos: Dzięki wielkie :D
Wiesz może czemu w tym przypadku mam prace O(n*logn)
Jak podstawie sobie log n do drugiej petli to mam n/2 < i <= n, czyli to licze jako n operacji?

[leoha]

@ronek22: "praca"? Co to za nomenklatura? Znowu jakiś profesorek na studiach probuje definiowac swoje nazwy na nowo?

[ronek22]

@leoha: Spokojnie, w algorytmach równoległych jest to rozdzielone na czas i prace właśnie

[mk321]

@leoha: @ronek22: tak to jest jak matematycy i fizycy biorą się za informatykę. Algorytmy definiuje się przez pracę... a jednostka to dżul.

[mk321]

@leoha: jak w sieci będą duże pingi, to znaczy, że Ethernet jest wolny w opór... wyrażone w Omach.