[Goglez]

Pytanie o notację dużego O: jeśli na danych składających się z n bitów robię coś co ma złożoność obliczeniową n log(n), a do tego jeszcze dodatkowo x log(n), gdzie x to jakaś stała, to wtedy złożoność mam O(n log(n) + x log(n)) czy to się redukuje do O(nlog(n)) czy jak?

#algorytmy #informatyka #programowanie

[GeDox]

@Goglez: jak chcesz zredukować stałą?

[cordianss]

@Goglez: A liczysz złożoność od N czy od X?

[sasik520]

Stała to stała, w notacji dużego O nie ma znaczenia. Wykres nlog(n) przemnożony przez jakąś stała od któregoś miejsca ograniczy nlogn + Xlogn, a przemnożony przez inną stała - od dołu.

[ly000]

@Goglez: do O(nlogn) się redukuje
ale czasami się rozpisuje tak dłużej tak jak ty pokazałeś, np. żeby pokazać jak się to liczy.

[Saly]

@Goglez: ogarnij Zależności algebraiczne tu https://pl.wikipedia.org/wiki/Asymptotyczne_tempo_wzrostu . Przy takiej granicy do nieskończoności wszystkie czynniki rosnące wolniej (w zależności od N) redukują się do zera.