Big Oh notation

Question

Potrzebuję potwierdzenia na coś naprawdę szybko. Jeśli testowanie algorytmu trwa od n(n-1)/2, to czy jest to wielki numer O(n^2)?

Answer 1

n (n-1)/2 rozszerza się (n^2 -n)/2, czyli (n^2/2) - (n/2)

(n^2/2) i (n/2) są dwa składniki funkcji, z których dominuje n^2/2. Dlatego możemy zignorować część - (n/2).

Od n^2/2 można bezpiecznie usunąć część/2 w asymptotycznej analizie notacji.

Upraszcza do n^2

Dlatego tak, to jest w czasie O (n^2)

Answer 2

Tak, zgadza się.

n(n-1)/2 rozszerza się n^2/2 - n/2:

Określenie liniowy n/2 spada ponieważ jest niższego rzędu. Pozostawia to n^2/2. Stała zostaje wchłonięta przez big-O, pozostawiając n^2.

Answer 3

Tak:

n(n-1)/2 = (n2-n)/2 = O(n^2) 

Answer 4

Tak, to prawda. n(n-1)/2 jest (n^2 - n)/2, która jest wyraźnie mniejsza niż c*n^2 dla wszystkich n>=1 jeśli wybrać c to przynajmniej 1.